Java数据结构第十五期：走进二叉树的奇妙世界(四)

专栏：Java数据结构秘籍

个人主页：手握风云

目录

一、二叉树OJ练习题（续）

1.1. 二叉树的层序遍历

1.2. 二叉树的最近公共祖先

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

1.4. 从中序与后序遍历序列构造二叉树

1.5. 根据二叉树创建字符串

一、二叉树OJ练习题（续） 1.1. 二叉树的层序遍历

     层序遍历，就是从左到右依次访问每个节点。这里我们要借助队列来非递归方式的实现。我们先将根结点root放入队列，再用cur引用来接收弹出的根结点最后再打印。当左右子树不为空时，再一次将左子树和右子树放入队列中。然后先弹出左子树，如果左子树的左右结点不为空，再次放入。当队列为空时，遍历过程结束。所以下面这棵二叉树的打印结果应为“4271369”。

import java.util.LinkedList; import java.util.Queue; class TreeNode{ public int val; public TreeNode left; public TreeNode right; public TreeNode() {} public TreeNode(int val) { this.val = val; } public TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right import java.util.LinkedList; import java.util.Queue; class TreeNode{ public int val; public TreeNode left; public TreeNode right; public TreeNode() {} public TreeNode(int val) { this.val = val; } public TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } } public class Solution { public void levelOrder(TreeNode root){ Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.offer(root); while(! queue.isEmpty()){ TreeNode cur = queue.poll(); System.out.print(cur.val+" "); if(cur.left != null){ queue.offer(cur.left); } if(cur.right != null){ queue.offer(cur.right); } } } }= right; } } public class Solution { public void levelOrder(TreeNode root){ Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.offer(root); while(! queue.isEmpty()){ TreeNode cur = queue.poll(); System.out.print(cur.val+" "); if(cur.left != null){ queue.offer(cur.left); } if(cur.right != null){ queue.offer(cur.right); } } } } public class Test { public static void main(String[] args) { TreeNode root = new TreeNode(4,new TreeNode(2),new TreeNode(7)); root.left.left = new TreeNode(1); root.left.right = new TreeNode(3); root.right.left = new TreeNode(6); root.right.right = new TreeNode(9); Solution solution = new Solution(); solution.levelOrder(root); } }

       但题目当中给出的类型是嵌套List<List<Integer>>，同时根据输出的格式来，创建一个二维数组，第一层放入第一列中。我们依然可以借助上面的队列来实现。与上面的方法类似，我们还需要再定义一个整型size变量来接受队列的长度，根据队列的长度来选择弹出与进入的操作。

public List<List<Integer>> levelOrder1(TreeNode root){ List<List<Integer>> ret = new ArrayList<>(); if(root == null) return ret; Queue<TreeNode> queue1 = new LinkedList<TreeNode>(); queue1.offer(root); while(! queue1.isEmpty()){ List<Integer> curList = new ArrayList<>(); int size = queue1.size(); while(size != 0){ TreeNode cur = queue1.poll(); curList.add(cur.val); if(cur.left != null){ queue1.offer(cur.left); } if(cur.right != null){ queue1.offer(cur.right); } size--; } ret.add(curList); } return ret; } import java.util.List; public class Test { public static void main(String[] args) { Solution solution = new Solution(); TreeNode root = new TreeNode(4,new TreeNode(2),new TreeNode(7)); root.left.left = new TreeNode(1); root.left.right = new TreeNode(3); root.right.left = new TreeNode(6); root.right.right = new TreeNode(9); solution.levelOrder(root); List<List<Integer>> result = solution.levelOrder1(root); System.out.println(result); } } 1.2. 二叉树的最近公共祖先

        如果是上图中第三种情况，那么我们就直接返回root。如果是第一种情况，当root向下遍历时，遇到p、q结点时，直接返回到root（如下图所示）。

        如果是第二种情况，当root遍历到p节点时，5结点返回p的地址，同时我们也可以找到q结点并返回。但还是有一种极端情况，q是孩子节点p的一个子结点。按照上面的思路，直接就返回这个结点。所以这种极端情况可以总结为，只要root遍历到p或者q中一个，直接返回对应的结点。因为p、q都在同一棵子树上，当root去遍历另一棵子树时，会返回null，所以最终结果是p，与p或q在根节点上是类似的。

        完整代码实现：

class TreeNode{ public int val; public TreeNode left; public TreeNode right; public TreeNode() {} public TreeNode(int val) { this.val = val; } public TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } } public class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){ if(root == null){ return root; } if(root == p || root == q){ return root; } TreeNode leftT = lowestCommonAncestor(root.left,p,q); TreeNode rightT = lowestCommonAncestor(root.right,p,q); if(leftT != null && rightT != null){//p、q分别在左右子树上 return root; }else if(leftT != null){ return leftT; } else if (rightT != null) { return rightT; } return null; } } public class Test { public static void main(String[] args) { TreeNode root = new TreeNode(3,new TreeNode(5),new TreeNode(1)); root.left.left = new TreeNode(6); root.left.right = new TreeNode(2,new TreeNode(7),new TreeNode(4)); root.right.left = new TreeNode(0); root.right.right = new TreeNode(8); TreeNode p = root.left; TreeNode q = root.right; Solution solution = new Solution(); TreeNode cur = solution.lowestCommonAncestor(root,p,q); System.out.println(cur.val); } }

        这道题还有另一种做法：如果我们把二叉树里的每一个结点新增加一个前驱域，用来存储父节点的地址，那么这道题的思路就变成了一链表交点的形式来求最近的公共祖先结点。可是定义的TreeNode类里面的成员变量里面没有这个变量。此时可以利用两个栈来存储从root到p、q结点路径上的结点。

        基本思路：只要root不为空，就把结点扔进栈当中。让长度较大的栈先弹出一定的元素，使得两个栈长度相等。两个栈再同时弹出元素，判断两个值是否相等，相等则是最近的公共祖先结点。

        而下面问题又来了，我们该如何求路径上的结点？只要root不等于p或者q，就将该节点放进栈中并继续递归；当root等于p或者q时，就停止。如果在遍历过程中某一个结点既不等于p、q，且左右都为空，那么这个元素就会被弹出。

        完整代码实现：

import java.util.Stack; class TreeNode{ public int val; public TreeNode left; public TreeNode right; public TreeNode() {} public TreeNode(int val) { this.val = val; } public TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } } public class Solution { public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack){ if(root == null){ return false; } stack.push(root); if(root == node){ return true; } boolean flag = getPath(root.left,node,stack); if(flag){ return true; } flag = getPath(root.right,node,stack); if(flag){ return true; } stack.pop(); return false; } public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){ if(root == null){ return null; } Stack<TreeNode> stack1 = new Stack<>(); Stack<TreeNode> stack2 = new Stack<>(); getPath(root,p,stack1); getPath(root,q,stack2); int len1 = stack1.size(); int len2 = stack2.size(); int len = len1 - len2; if(len < 0){ len = Math.abs(len); while(len != 0){ stack2.pop(); len--; } }else{ while(len != 0){ stack1.pop(); len--; } } //保证两个栈的长度一样 while (!stack1.isEmpty() && !stack2.isEmpty()){ if(stack1.peek() == stack2.peek()){ return stack1.pop(); }else{ stack1.pop(); stack2.pop(); } } return null; } } public class Test { public static void main(String[] args) { TreeNode root = new TreeNode(3,new TreeNode(5),new TreeNode(1)); root.left.left = new TreeNode(6); root.left.right = new TreeNode(2,new TreeNode(7),new TreeNode(4)); root.right.left = new TreeNode(0); root.right.right = new TreeNode(8); TreeNode p = root.left; TreeNode q = root.right; Solution solution = new Solution(); TreeNode cur = solution.lowestCommonAncestor(root,p,q); System.out.println(cur.val); } } 1.3. 从前序与中序遍历序列构造二叉树

        基本思路：1.遍历前序遍历的数组，遇到元素之后，在中序遍历数组当中找到该数字；2.该数字的左边就是左树，右边就是右树。上述两步构成一个递归来构造子树。

        我们以中序遍历的数组的第一个元素ibegin，最后一个元素iend之间找到二叉树的根，因为是前序遍历，先有的左树再有的右树，那么左边的区间就会是(9,x) = (ibegin,iend)，iend = iroot-1；相反我们去递归右树，ibegin=iroot+1。也就是说，递归根结点创建左树和右树时，还需要知道ibegin和iend的范围。

        我们还需要额外创建一个方法来接受ibegin和iend的参数。创建root，利用buildTreeChild方法递归来创建根结点的左树和右树。可我们不知道中序遍历的数组中根结点的下标，还需要一个方法来查找根结点的下标。

public class Solution { public TreeNode buildTree(int[] preorder, int[] inorder){ return buildTreeChild(preorder,0,inorder,0, inorder.length-1); } public TreeNode buildTreeChild(int[] preorder, int prevIndex,int[] inorder, int inbegin, int inend){ TreeNode root = new TreeNode(preorder[prevIndex]); int rootIndex = findIndex(inorder,inbegin,inend,preorder[prevIndex]); prevIndex++; root.left = buildTreeChild(preorder,prevIndex,inorder,inbegin,rootIndex-1); root.right = buildTreeChild(preorder,prevIndex,inorder,rootIndex-1,inend); return root; } private int findIndex(int[] inorder,int inbegin,int inend,int key) { for(int i = inbegin; i <= inend; i++) { if(inorder[i] == key) { return i; } } return -1; } }

        但此时的代码还是有一点逻辑上的问题，就是递归结束的条件是什么？一棵二叉树，总有一棵子树的左右子树都为空。但我们上面的代码没有null。所以要处理一下边界情况：

if(inbegin > inend){ return null; }

        还存在另一个问题，就是局部变量的定义。因为二叉树遍历完左树的时候，最后给根返回0，从0再去遍历右子树。所以我们把prevIndex定义为成员变量。

        完整代码实现： 

class TreeNode{ int val; TreeNode left; TreeNode right; public TreeNode() {} public TreeNode(int val) { this.val = val; } public TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } } public class Solution { public int prevIndex; public TreeNode buildTree(int[] preorder, int[] inorder){ return buildTreeChild(preorder,inorder,0, inorder.length-1); } public TreeNode buildTreeChild(int[] preorder, int[] inorder, int inbegin, int inend){ if(inbegin > inend){ return null; } TreeNode root = new TreeNode(preorder[prevIndex]); int rootIndex = findIndex(inorder,inbegin,inend,preorder[prevIndex]); prevIndex++; root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1); root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend); return root; } private int findIndex(int[] inorder,int inbegin,int inend,int key) { for(int i = inbegin; i <= inend; i++) { if(inorder[i] == key) { return i; } } return -1; } } public class Test { public static void PrintTreeNode(TreeNode root){ if(root == null){ return; } System.out.print(root.val+" "); PrintTreeNode(root.left); PrintTreeNode(root.right); } public static void main(String[] args) { Solution soluion = new Solution(); int[] preOrder = new int[]{3,9,20,15,7}; int[] inOrder = new int[]{9,3,15,20,7}; TreeNode root = soluion.buildTree(preOrder,inOrder); PrintTreeNode(root); } } 1.4. 从中序与后序遍历序列构造二叉树

        与上面一题的思路一样，但后序遍历的顺序是“左子树、右子树、根”，那根结点从后面开始找。并且在创建树的过程中，要先创建右树再创建左树。

class TreeNode{ int val; TreeNode left; TreeNode right; public TreeNode() {} public TreeNode(int val) { this.val = val; } public TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } } public class Solution { public int postIndex = 0; public TreeNode buildTree(int[] inorder, int[] postorder){ postIndex = postorder.length-1; return buildTreeChild(postorder,inorder,0, inorder.length-1); } public TreeNode buildTreeChild(int[] preorder, int[] inorder, int inbegin, int inend){ if(inbegin > inend){ return null; } TreeNode root = new TreeNode(preorder[postIndex]); int rootIndex = findIndex(inorder,inbegin,inend,preorder[postIndex]); postIndex--; root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend); root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1); return root; } private int findIndex(int[] inorder,int inbegin,int inend,int key) { for(int i = inbegin; i <= inend; i++) { if(inorder[i] == key) { return i; } } return -1; } } public class Test { public static void PrintTreeNode(TreeNode root){ if(root == null){ return; } PrintTreeNode(root.left); PrintTreeNode(root.right); System.out.print(root.val+" "); } public static void main(String[] args) { Solution solution = new Solution(); int[] Inorder = new int[]{9,3,15,20,7}; int[] Postorder = new int[]{9,15,7,20,3}; TreeNode root = solution.buildTree(Inorder,Postorder); PrintTreeNode(root); } }

 

1.5. 根据二叉树创建字符串

        通过上图分析：当1的左子树不为空，就用一个(，2的左子树也不为空，也使用一个(，4再往下递归返回null，直接)闭合；2的右子树为null，返回)；1的右子树不为空，返回(，3递归返回null，直接)闭合。

        所以我们可以总结下来规律：当子树不为空时，直接加左括号；当root的左树为空，且右树也为空，直接加右括号闭合；当root的左树不为空，右树为空，也加右括号闭合。

public void tree2strChild(TreeNode root,StringBuilder stringBuilder){ if(root == null){ return; } stringBuilder.append(root.val); //判断根的左子树 if(root.left != null){ stringBuilder.append("("); tree2strChild(root.left,stringBuilder);//递归左树 stringBuilder.append(")");//左树走完，右括号闭合 }else { if(root.right == null){ return;//因为4结点走完，返回2结点，这里本身就会加一个")" }else { } } //判断根的右子树 if(root.right != null){ stringBuilder.append("("); tree2strChild(root.right,stringBuilder); stringBuilder.append(")"); }else { } }

        但也存在另一种情况：如果子树的左边为空，右边不为空，就直接加一对小括号，再去递归右树，把4再加进去。再继续往下走，如果root.right为空，正好符合上面2结点的情况：2的左边走完，右边为空，直接return加右括号。所以只要左树为空，右树不为空，就不做任何处理。

        完整代码实现：

class TreeNode{ public int val; public TreeNode left; public TreeNode right; public TreeNode() {} public TreeNode(int val) { this.val = val; } public TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } } public class Solution { public String tree2str(TreeNode root){ StringBuilder stringBuilder = new StringBuilder(); tree2strChild(root,stringBuilder); return stringBuilder.toString(); } public void tree2strChild(TreeNode root,StringBuilder stringBuilder){ if(root == null){ return; } stringBuilder.append(root.val); //判断根的左子树 if(root.left != null){ stringBuilder.append("("); tree2strChild(root.left,stringBuilder);//递归左树 stringBuilder.append(")");//左树走完，右括号闭合 }else { if(root.right == null){ return;//因为4结点走完，返回2结点，这里本身就会加一个")" }else { stringBuilder.append("()"); } } //判断根的右子树 if(root.right != null){ stringBuilder.append("("); tree2strChild(root.right,stringBuilder); stringBuilder.append(")"); }else { return; } } } public class Test { public static void main(String[] args) { Solution solution = new Solution(); TreeNode root1 = new TreeNode(1,new TreeNode(2),new TreeNode(3)); root1.left.left = new TreeNode(4); TreeNode root2 = new TreeNode(1,new TreeNode(2),new TreeNode(3)); root2.left.right = new TreeNode(4); System.out.println(solution.tree2str(root1)); System.out.println(solution.tree2str(root2)); } }