Java数据结构之二叉树经典面试OJ题

二叉树遍历 二叉树的层序遍历 二叉树的最近公共祖先 二叉搜索树与双向链表 从前序与中序遍历序列构造二叉树

---

1、二叉树遍历

题目描述:

示例1

输入:abc##de#g##f###
输出：c b e g d f a

题目分析:
  题目给定一个字符串，这个字符串是一个先序遍历结果(’ # ’ 代表当前节点为空)，题目要求我们根据这个字符串创建二叉树并打印中序遍历结果，我们只需:

遍历字符串，字符串当前位置的值不为空时，创建节点，并继续向后遍历字符串当前位置的值为空时，直接向后遍历创建完二叉树后对二叉树进行中序遍历，并打印中序遍历结果即可

代码实现:

import java.util.*;class TreeNode{ char val; TreeNode left; TreeNode right; public TreeNode(char val){ this.val = val; }}public class Main{ static int i = 0;// i 用在createTree()中，用于遍历字符串 public static void main(String[] args){ Scanner scanner = new Scanner(System.in); String str = scanner.nextLine();//输入字符串 TreeNode root = createTree(str);//创建二叉树 middle(root);//中序遍历 } //createTree()方法根据输入的字符串创建二叉树，root用于保存二叉树大的根 public static TreeNode createTree(String str){ if(str == null) return null; TreeNode node = null; if(str.charAt(i) != '#'){ //当字符串中当前位置的值不等于'#'时，创建节点 node = new TreeNode(str.charAt(i)); ++i;//每次创建完节点之后++i，后面的值为root.left.val; node.left = createTree(str); node.right = createTree(str); }else{ ++i; } return node; } //middle()用于二叉树的中序遍历并打印遍历结果 public static void middle(TreeNode root){ if(root == null) return; middle(root.left); System.out.print(root.val+" "); middle(root.right); }}

结果:

2、二叉树的层序遍历

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例2:

输入：root = [1]
输出：[[1]]

示例3:

输入：root = []
输出：[]

思路分析:
  使用队列来保存当前层中的元素:

先将二叉树的根节点入队列依次将队首元素出队列，并判断这个节点的左右子树是否为空，将不为空的子树入队在每次入队前判断队列的长度，队列长度即等于当前层的元素个数，每次出队后将元素加入当前层的list中每将一层走完之后，将这层元素所在的list加入到总的list中

代码实现:

class Solution { public List> levelOrder(TreeNode root) { List> lists = new ArrayList(); if(root == null) return lists; Queue queue = new linkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); List list = new ArrayList<>(); while(size != 0){ TreeNode treeNode = queue.poll(); list.add(treeNode.val); if(treeNode.left!=null){ queue.offer(treeNode.left); } if(treeNode.right!=null){ queue.offer(treeNode.right); } --size; } lists.add(list); } return lists; }}

结果:

3、二叉树的最近公共祖先

题目:

示例1:

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例2:

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例3:

输入：root = [1,2], p = 1, q = 2
输出：1

题目分析:
求两个节点的最近公共祖先，共有以下几种情况:

当根节点为空时，证明该二叉树为空，返回null当二叉树不为空时，如果p和q之间有任意一个节点等于根节点，则根节点就是这两个节点的最近公共祖先二叉树不为空且p、q都不等于根节点，此时又分以下情况:如果根节点的左右两侧各有一个节点，则根节点就是p、q的最近公共祖先；如果p、q在根节点的的同一侧，此时通过递归找到公共祖先

实现代码:

class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root == null) return null; if(root == p || root == q){ return root; } //走到这里说明root不等于p或q，则p和q一定在root的子树当中 //下面判断p和q的具体位置 TreeNode le = lowestCommonAncestor(root.left,p,q); TreeNode ri = lowestCommonAncestor(root.right,p,q); //如果le = null,说明p,q都在root的右子树当中，return ri; //同理，如果ri = null，则p,q都在root的左子树当中，return le; if(le == null) return ri; if(ri == null) return le; //走到这里说明p和q位于root的两侧，则他们的最近公共祖先为root return root; }}

结果:

二叉搜索树与双向链表

题目:

输入描述：
 二叉树的根节点

返回值描述：
 双向链表的其中一个头节点。

示例1:

输入：
{10,6,14,4,8,12,16}
返回值：From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4;
说明：
输入题面图中二叉树，输出的时候将双向链表的头节点返回即可。

示例2:

输入：
{5,4,#,3,#,2,#,1}
复制
返回值：
From left to right are:1,2,3,4,5;From right to left are:5,4,3,2,1;
复制
说明：
          5
         /
        4
       /
      3
     /
    2
    /
  1
 树的形状如上图

题目分析:
  要得到有序的双向链表，我们只需中序遍历二叉树，并修改节点的指向即可。

代码实现:

public class Solution {//中序遍历并修改节点指向 TreeNode prev = null; public void inOrder(TreeNode pRootOfTree){ if(pRootOfTree == null) return; inOrder(pRootOfTree.left); //修改指向 pRootOfTree.left = prev; if(prev != null){ prev.right = pRootOfTree; } prev = pRootOfTree; inOrder(pRootOfTree.right); } public TreeNode Convert(TreeNode pRootOfTree) { if(pRootOfTree == null) return null; inOrder(pRootOfTree); //找到双向链表的头结点 TreeNode head = pRootOfTree; while(head.left != null){ head = head.left; } return head; }}

结果:

PS: 好高的比例。。。

从前序与中序遍历构造二叉树

示例1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

题目分析:
根据前序与中序序列构造二叉树，具体思路是:

找到前序序列的第一个节点，该节点为二叉树的根节点在中序遍历序列中找到这个根节点，这个根节点的左边为这个节点的左子树，右边为这个节点的右子树向后遍历前序序列，重复上述操作即可

代码实现:

class Solution { public int preIndex = 0;//preIndex为前序遍历时的下标 //preorder为前序遍历序列，inorder为中序遍历序列 public TreeNode buildTree(int[] preorder, int[] inorder) { if(preorder.length == 0 || inorder.length == 0){ return null; } return createTree(preorder,inorder,0,inorder.length-1); } //创建二叉树 //inBegin为中序遍历中当前节点的子树的起始位置，inEnd为终止位置 public TreeNode createTree(int[] preorder, int[] inorder, int inBegin, int inEnd){ //当前序遍历完成时退出递归，也是递归的终止条件 if(preIndex == preorder.length) return null; //创建节点 TreeNode root = new TreeNode(preorder[preIndex]); //查找前序序列中的元素在中序序列中的位置，用rootIndex接收 int rootIndex = findIndex(inorder,inBegin,inEnd,preorder[preIndex]); //rootIndex等于-1是指在中序序列中没有找到前序序列中的元素，此时返回null if(rootIndex == -1) return null; //每次查找完成后，将遍历前序序列的下标向后移动 ++preIndex; //当前节点创建完成后，创建其左右孩子节点 root.left = createTree(preorder,inorder,inBegin,rootIndex-1); root.right = createTree(preorder,inorder,rootIndex+1,inEnd); //创建完成后，返回二叉树的根 return root; } //查找先序遍历序列中的节点在中序遍历序列中的位置 public int findIndex(int[] inorder,int inBegin, int inEnd, int val){ //在中序序列中查找到，返回该元素所在的下标 for(int i = inBegin;i<=inEnd;++i){ if(inorder[i] == val){ return i; } } //没有查找到，返回-1 return -1; }}

结果:

---

The End