java数据结构_二叉树的相关面试题_5.6

1. 检查两颗树是否相同。

力扣链接：100. 相同的树 - 力扣（LeetCode）

首先要理解题意：相同指的是两棵树的 结构 和 数值 均是相同的。

如下图：p 和 q两棵树 结构和其每个结点的数值均相同，才是两棵相同的树

如下图：q这棵树的结构，与p对比来讲，少了根为1的左结点，则不是两棵相同的树

如下图：q的根结点的值与p不同，则不是两棵相同的树

总结下来：不相同有两种情况：

1.一棵树的某棵子树为空，另一棵树的对应的那棵子树不为空，如下图：

2.虽然两棵树都不为空，但其值不相同

所以判断两棵树是否相同，也是需要对两棵树分别进行遍历，考虑到前序遍历根先后的顺序比较方法，于是有如下代码：

public boolean isSameTree(TreeNode p, TreeNode q) {//如果两棵树中，一棵为空，另一课非空，则一定不相同if((p != null && q == null) || (p == null && q != null)) {return false;}//如果两棵树均为空，则相同if(p == null && q == null) {   return true;}//代码执行到这里，两棵树一定都不为nullif(p.val != q.val) {return false;}return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

注意代码的顺序一定要检查是否为空，然后再对于检查p.val和q.val是否相同。

还需要注意的是，最后判断的代码一定要判断是否不相同，反会false，不能判断是否相同，然后直接返回true，如果直接判断当前结点是否相同，然后直接返回true，就无法再向下递归树的左右子树是否相同了！

同样的，该代码的遍历过程仍可以像上篇文章一样模拟出来，此处省略...

补充，如果p树的结点个数为p，q树的结点个数为q，则该方法的时间复杂度为min(p,q)

2. 另一颗树的子树。

力扣链接：572. 另一棵树的子树 - 力扣（LeetCode）

首先要明白题意，给root树的根结点root，subRoot树的根结点subRoot，判断在root中，是否有subRoot结构。

如下图，在root树中有subRoot结构

如下图，在root树中则不包含subRoot树（多了一个0）

还有一种情况，如下图，root和subRoot相同，则也算在root树中包含subRoot，这样判断的话，不就是第一道题中的判断两树是否相同

如果最开始的root和sbuRoot不相同的话，则向下递归，看root的左子树和右子树和subRoot是否相同，这样就出现了递归的操作。

于是有如下代码：

因为是递归方法，所以肯定会递归的某棵树的子树为空，如果继续进行子树的子树进行递归，会出现空指针异常，所以要先判断root == null，防止空指针异常。然后需要使用第一道题的isSameTree方法，来判断当前结点为root的树是否和subRoot树相同。

注意，这样必须是直接判断两棵树是否相同，不可以 if(!isSameTree(root, subRoot)) return false; 不能直接当前树不包含subRoot就直接返回false，万一当前树的子树包含呢？

之后判断左子树和右子树递归是否包含subRoot，如果都没有返回true，则返回false

 完整代码为：

class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {// 如果两棵树中，一棵为空，另一课非空，则一定不相同if ((p != null && q == null) || (p == null && q != null)) {return false;}// 如果两棵树均为空，则相同if (p == null && q == null) {return true;}// 代码执行到这里，两棵树一定都不为nullif (p.val != q.val) {return false;}return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);}public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(root == null) {return false;}if(isSameTree(root, subRoot)) {return true;}if(isSubtree(root.left, subRoot)) {return true;}if(isSubtree(root.right, subRoot)) {return true;}return false;}
}

补充：假设 root树的结点的个数为 r，subRoot树的结点个数为s，则该方法的时间复杂度为        O(r * s)，因为，root的每一个结点都要遍历一下，看是否与subRoot树相同

3.反转二叉树

力扣链接：226. 翻转二叉树 - 力扣（LeetCode）

如下图，讲二叉树的每一个结点的左右子树都进行互换，注意，在进行交换的适合，是要将左右子树的对应的引用进行交换，而不是仅仅将引用中的值进行交换。

可以想到，需要创建一个中间变量tmp，tmp = 地址A，地址A = 地址B，地址B = tmp，于是有代码如下：

public TreeNode invertTree(TreeNode root) {if(root == null) return null;TreeNode tmp = root.left;root.left = root.right;root.right = tmp;invertTree(root.left);invertTree(root.right);return root;
}

 4. 平衡二叉树

力扣链接：110. 平衡二叉树 - 力扣（LeetCode）

平衡二叉树：每个节点的左子树和右子树的高度差的绝对值不超过 1，并且左右子树也都是平衡二叉树。

如下图：3的左子树高度为1，右子树高度为2，相差为1，9的左右子树均为0，相差为0，20的左右子树高度均为1，相差为0，15的左右子树均为0，相差为0，7的左右子树均为0，相差为0。所以该二叉树为平衡二叉树。

如下图，3的左子树的高度为4，右子树的高度为4，相差为0。9的左子树高度为2，右子树高度为0，相差为2，只要存在高度差的绝对值大于1的情况，则这棵二叉树就不是平衡二叉树。

所以，要实现该方法，纪要保证当前结点的左右节点的高度差小于1，也要保证该结点的左树是平衡的（递归）也要保证该结点的右树是平衡的（递归）。

求树的高度差的方法也在前面有所讲述，即getHeight方法。

于是有代码：

public int getHeight(TreeNode root) {if(root == null) return 0;int leftHeight = getHeight(root.left);int rightHeight = getHeight(root.right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}public boolean isBalanced(TreeNode root) {if(root == null) return true;int leftHeight = getHeight(root.left);int rightHeight = getHeight(root.right);return Math.abs(leftHeight - rightHeight) <= 1 && isBalanced(root.left)               && isBalanced(root.right);
}

将上述代码在力扣中可以正常通过检查，但要考虑一个问题，上述代码是否做了很多的冗余计算，例如下面这幅图，在getHeight方法中，要遍历一次整个二叉树，在isBalanced的递归中，又要遍历一次二叉树，遍历一次二叉树的时间复杂度为O(n)，这样就使得该方法的时间复杂度为O(n^2)。

仔细观察，在获取高度的适合，遍历到根结点为9的子树的时候，其9为根结点的左子树的高度为2，右子树的高度为0，已经发现了不符合平衡二叉树的定义，就不用再在isBalanced方法中遍历这里了。

可以在求高度的过程当中，就知道，这棵树是否平衡。

于是有如下代码：

public int getHeight(TreeNode root) {if(root == null) return 0;int leftHeight = getHeight(root.left);int rightHeight = getHeight(root.right);if(leftHeight >= 0 && rightHeight >= 0 &&Math.abs(leftHeight - rightHeight) <= 1) {return Math.max(leftHeight,rightHeight) + 1;} else {return -1;        }
}public boolean isBalanced(TreeNode root) {if(root == null) return true;return getHeight(root) > 0;
}

这样就可以在求高度的过程当中，检查这棵树是否平衡，如果是平衡，正常返回高度，如果不平衡直接返回-1，在isBalanced方法中，直接以是否大于0做检查即可判断！

5. 对称二叉树

力扣链接：101. 对称二叉树 - 力扣（LeetCode）

判断二叉树是否对称，就要知道非对称就哪几种情况，如下图：

三种情况为非对称的情况：前两种为结构非对称，即一边有结点，一边无结点，第三种即是结点的元素值不同。

当判断完一棵树的左右子树是否为上述三种情况，再进行递归其左右子树的左右子树是否对称，形成递归。最终如果左子树的左子树与右子树的右子树相同，左子树的右子树与右子树的左子树相同，返回true。

这三种情况可以对比于第一题，检查两棵树是否相同。

于是有代码如下：

public boolean isSymmetric(TreeNode root) {if(root == null) return true;return isSymmetricChild(root.left, root.right);
}public boolean isSymmetricChild(TreeNode leftTree, TreeNode rightTree) {if((leftTree == null && rightTree != null) ||(leftTree != null && rightTree == null)) {return false;}if(leftTree == null && rightTree == null) {return true;}if(leftTree.val != rightTree.val) {return false;}return isSymmetricChild(leftTree.left, rightTree.right) && isSymmetricChild(leftTree.right, rightTree.left);
}

6. 二叉树的构建及遍历

牛客链接：二叉树遍历_牛客题霸_牛客网

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。

例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

如题，给了一个字符串，则可以用i去遍历字符串，只要不是#就一定是结点，是结点就一定有左右子树，模拟图如下：

在牛客刷题网站中的ACM模式中，需先将准备工作做好，即创建TreeNode内部类

class TreeNode {char val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(char val) {this.val = val;}
}

因为题目要求是输入前序遍历顺序的字符串，然后以中序遍历的顺序打印出来，所以在main方法中的框架如下：

//测试类中：
public static void main(Strings[] args) {Scanner in = new Scanner(System.in);while(in.hasNextLine()) { //因为此处输入的是字符串，所以要用hasNextLine！！！String str = in.nextLine(); Main test = new Main(); //new一个test对象TreeNode root = test.createTree(str); //调用createTree方法test.inOrder(root); //调用打印方法}
}

其中inOrder中序遍历方法之前已经写过，此处仅放代码如下：

public void inOrder(TreeNode root) {if(root == null) return null;inOrder(root.left);System.out.print(root.val + " ");inOrder(root.right);}

重点是createTree方法：首先要接收字符串，所以参数为String str，然后用 i 遍历给的字符串（注意，这里并不是之前的那种用一个i来遍历数组，此时给的字符串是树前序遍历，所以i不会越界），于是有代码如下：

public int i = 0; //i为成员变量！！！
public TreeNode createTree(String str) {TreeNode root = null;if(str.charAt(i) != '#') { //如果不为空，创建新的结点root = new TreeNode(str.charAt(i));  //前序遍历，都是根结点，不断new新的TreeNode结点i++; //i向后遍历字符串//注意，向后递的过程是一直创建结点的过程，往回归的时候才是结点直接进行连接的过程root.left = createTree(str);root.right = createTree(str);} else {//遇到'#' 即遇到空，继续向后走i++;}return root; //最终返回根结点，因为递归中的归操作是结点之间创建连接的过程，所以最终会回归到根结点
}

牛客完整代码如下：

import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {class TreeNode {char val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(char val) {this.val = val;}}public int i;public  TreeNode createTree(String str) {TreeNode root = null;if (str.charAt(i) != '#') {root = new TreeNode(str.charAt(i));i++;root.left = createTree(str);root.right = createTree(str);} else {i++;}return root;}public  void inOrder(TreeNode root) {if (root == null) return;inOrder(root.left);System.out.print(root.val + " ");inOrder(root.right);}public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) {String str = in.nextLine();Main main = new Main();TreeNode root = main.createTree(str);main.inOrder(root);}}
}

7. 二叉树的层序遍历

力扣连接：102. 二叉树的层序遍历 - 力扣（LeetCode）

先不按照链接题目中的返回一个List<List<Integer>>写，可以先看一下层序遍历打印。

在二叉树的层序遍历中，可以不适用递归，而是用队列这种数据结构。

先将二叉树的根结点放入队列

然后再将A打印，并弹出赋给cur 

再将cur的left和right入队

再将B打印，并且出队，赋给cur，同时再把cur（此时cur为B）的left和right入队

再将C打印，并出队，赋给cur，同时将cur（此时cur为C）的left和right入队

再将D打印，并出队，赋给cur，同时将cur（此时为D）的left和right（D的left和right为空）入队

再将E打印，并出队，赋给cur，同时将cur（此时为E）的left（为空）和right（H）入队

再将F打印，并出队，赋给cur，同时将cur（此时为F）的left和right（均为空）入队

再将G 和 H按照上面流程打印出队，将其左右子树入队...

这样就模拟实现了用队列实现二叉树层序遍历的过程。

于是有代码如下：

如果该方法的返回值为List<List<TreeNode>>，即要返回如下图的结构

于是有代码：

先创建一个List<List<TreeNode>>的ret Queue<TreeNode>的队列，还是像上面层序遍历一样，看队列是否不为空，不为空，这里需要先记录队列的大小，然后定义一个tmp存放每一次的结点，size!=0进入循环，出队一个元素，size--，就可以把这一层的结点出队，size = 0的时候，里面的循环结束，一层遍历结束，将每一层的tmp添加到ret中即可！

力扣代码：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> ret = new ArrayList<>();if(root == null) return ret;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while(!queue.isEmpty()) {//先求当前队列的大小int size = queue.size();List<Integer> tmp = new ArrayList<>();while(size != 0) {//出队size次，就把当前这一层的结点全部出队了TreeNode cur = queue.poll();tmp.add(cur.val);size--;if(cur.left != null) {queue.offer(cur.left);}if(cur.right != null) {queue.offer(cur.right);}}ret.add(tmp);}return ret;}
}

8. 判断一棵树是不是完全二叉树

该题无刷题链接，可以逐步分析：

如下图，该二叉树是一个完全二叉树

仍然像第7题层序遍历一样，将根结点A入队

再出队，将出队的值赋给cur，再将cur的left和right入队

再将下一个结点B出队，将出队的值赋给cur，再将cur的left和right入队

再将下一个结点C出队，将出队的值赋给cur，再将cur的left和right入队

再将下一个结点D出队，将出队的值赋给cur，再将cur的left和right入队

再将下一个结点E出队，将出队的值赋给cur，再将cur的left和right入队

继续出队，如果出队的元素是null，且整个队列都是null，则证明该二叉树为完全二叉树。

如下图，非完全二叉树

流程：

当出队的元素是null，且此时的队列元素存在非null的元素，则该二叉树就不是完全二叉树

补充：null添加到队列中，是拥有一个大小空间的，属于一个元素。

在IDEA中测试如下图，添加了四个null，size为4，且queue非空

于是有代码如下：

public boolean isCompleteTree(TreeNode root) {if(root == null) return true;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while(!queue.isEmpty()) {TreeNode cur = queue.poll();if(cur != null) {queue.offer(cur.left);queue.offer(cur.right);} else {//此时遇到nullbreak;}}while(!queue.isEmpty()) {TreeNode cur = queue.poll();if(cur != null) {return false;}}return true;
}

9. 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先

力扣链接：236. 二叉树的最近公共祖先 - 力扣（LeetCode）

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

如下图：参数如果为5，1，则5 和 1的最近公共祖先则为3

若输入的参数为5，4，则5 和 4的公共祖先为5，因为根据定义，最近公共结点祖先可以为结点本身

为讲明此题，这里引入一个二叉搜索树的概念：根的左边都是比根小的结点，根的右边都是比根大的结点，如下图，就是一个二叉搜索树。

针对此题，有如下三种情况：

1. p == root || q == root 则此时最近公共祖先为 p || q ，如下图：

2. p.val < root.val && q.val > root.val 此时p在root的左边，q在root的右边 则公共祖先是root

3. p.val < root.val && q.val < root.val 此时p和q在root的同一侧(左侧)。这种情况，就需要递归到root的左数当中去查找

递归过程：

于是有代码如下：

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null) return null;//如果当前的根结点root等于p或者q其中一个，则说明是第一种情况，当前根结点就是两个参数的公共祖先结点if(root == p || root == q) {return root;}TreeNode leftTree = lowestCommonAncestor(root.left, p, q);TreeNode rightTree = lowestCommonAncestor(root.right, p, q);if(leftTree != null && rightTree != null) {//如果leftTree 和 rightTree均不为null，则说明p和q分别位于当前根结点的左右子树中，此时就是第二种情况，当前根结点就是两个参数的公共祖先结点return root;} else if(leftTree != null) { //如果没进入上面的if，则说明leftTree和rightTree一定有一个是为null的，此时如果leftTree不为null，但rightTree为null，则说明p和q都位于左子树中，此时返回leftTreereturn leftTree;} else {return rightTree;}}

可以自己将三种情况画图，然后实操递归一下！

下面还有一种方法：

如果二叉树保存了父亲结点的地址，那么这个题就可以转变为求链表的相交结点

则要解决的问题是，如果找到root根结点到目标结点node路径之间的所有结点，存放在栈中

代码如下：

private boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {//边界条件检查：如果当前根节点 root 为 null 或者目标节点 node 为 null，说明无法继续查找路径，直接返回 false。if(root == null || node == null) {return false;}//将当前节点压入栈中：将当前根节点 root 压入栈 stack 中，表示该节点是路径的一部分。stack.push(root);/检查当前节点是否为目标节点：如果当前根节点 root 等于目标节点 node，说明已经找到了从根节点到目标节点的路径，返回 true。if(root == node) {return true;}//递归查找左子树：递归调用 getPath 方法在左子树中查找目标节点。如果在左子树中找到了路径（即 flg 为 true），则直接返回 true。boolean flgLeft = getPath(root.left, node, stack);if(flgLeft) {return true;}//递归查找右子树：若在左子树中未找到路径，则递归调用 getPath 方法在右子树中查找目标节点。如果在右子树中找到了路径（即 flg2 为 true），则直接返回 true。boolean flgRight = getPath(root.right, node, stack);if(flgRight) {return true;}//回溯操作：如果在当前节点的左子树和右子树中都未找到目标节点，说明当前节点不是路径的一部分，需要将其从栈中弹出（回溯操作），并返回 false。stack.pop();return false;
}

 以下为递归过程：

有了上面的方法，找公共祖先的方法就转换成了找两个栈中的公共结点方法了

public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {if(root == null) return null;Stack<TreeNode> stackP = new Stack<>();Stack<TreeNode> stackQ = new Stack<>();//通过getPath方法，分别将root到p和到q的路径的结点存储到了stackP和stackQ中getPath(root, p, stackP);getPath(root, q, stackQ);int sizeP = stackP.size();int sizeQ = stackQ.size();//下面操作，使得stackP和stackQ的结点数相同//且在下面操作中，并不会将公共祖先结点弹出//在该方法里，是先分别找到从根节点到节点 p 和节点 q 的路径，并将这些路径上的节点依次压入两个栈 stackP 和 stackQ 中。由于这两个栈存储的路径都是从根节点开始的，所以公共祖先节点必然处于路径的起始部分。if(sizeP > sizeQ) {int size = sizeP - sizeQ;while(size != 0) {stackP.pop();size--;}} else {int size = sizeQ - sizeP;while(size != 0) {stackQ.pop();size--;}}while(!stackP.isEmpty() && !stackQ.isEmpty()) {//检查是否为两个栈的公共结点if(stackP.peek().equals(stackQ.peek())) {return stackP.peek();}//该结点不是公共结点，弹出stackP.pop();stackQ.pop();}//如果弹出知道循环结束，有一个栈为空，还没有返回某个栈的peek，则说明两个栈没有公共结点，即没有公共祖先，返回nullreturn null;
}

如下为力扣完整代码：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {private boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {if (root == null || node == null) {return false;}stack.push(root);if (root == node) {return true;}boolean flg = getPath(root.left, node, stack);if (flg) {return true;}boolean flg2 = getPath(root.right, node, stack);if (flg2) {return true;}stack.pop();return false;}public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null) return null;Stack<TreeNode> stackP = new Stack<>();Stack<TreeNode> stackQ = new Stack<>();getPath(root, p, stackP);getPath(root, q, stackQ);int siezP = stackP.size();int siezQ = stackQ.size();if(siezP > siezQ) {int size = siezP - siezQ;while(size != 0) {stackP.pop();size--;}} else {int size = siezQ - siezP;while(size != 0) {stackQ.pop();size--;}}while(!stackP.isEmpty() && !stackQ.isEmpty()) {if(stackP.peek().equals(stackQ.peek())) {return stackP.peek();}stackP.pop();stackQ.pop();}return null;}
}

 10. 根据一棵树的前序遍历与中序遍历构造二叉树

力扣链接：105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

此题是将之前的选择题，要求以代码的形式转换出来

如下图，定义一个下标pi，遍历先序遍历，在中序遍历中定义ib(i begin)，ri(root i)，ie(i end)，在中序遍历中ib -- ie 中找到先序遍历pi对应的元素ri，然后创建二叉树

然后递归创建左子树（ie = 之前的ri - 1）和右子树（ib = 之前的ri + 1）

力扣初始代码如下，由上述分析，需要得到下标的参数，但给出的buildTree方法中没有下标参数，所以需要再创建一个方法

再创建一个buildTreeChild方法，将相关下标作为参数传入，最终正在buildTree方法中返回其结果即可，再buildTree中，调用buildTreeChild方法时候，传入的下标参数中，inend传入的是inorder.length - 1，注意边界问题

由刚刚分析，再buildTreeChild方法中，一定是会使用递归的，使用递归，就一定要想清楚，使递归结束的条件

当创建完F这棵树之后，在创建H这棵左子树的时候，其ie 为 ri -1，即再创建H这棵子树的时候，H的ib 和 ie 相同了，当ie == ib的时候，说明此时只有一个结点了，但这个结点也是需要创建的。

再研究，如果F没有左子树，则ib就不会去走ri -1 ，ib会和ri相同，但是F有右子树I，右子树I进行创建的时候，ie = ri -1 这样的话，ib会 > ie ，则证得，如果 ib > ie 说明没有左子树

同样的，如果F没有右子树，ie就不会走ri + 1，但F有左子树，H子树创建的时候，ib = ri + 1，此时ib > ie ，则证得：如果ib > ie 说明没有右子树

从而证明：如果ib > ie 则没有左子树 或 右子树 这就是递归结束的条件

则有下面的第一步为判断递归结束的条件，第二步，由先序遍历数组来创建根结点

接下来第三步，在中序遍历中找到先序遍历中的根结点的下标，在findIndex方法中，for循环，循环结束条件是 i <= inend 因为传入参数inend的时候，inend = inorder.length - 1

如果下标为-1，则返回null（没有找到）

第四步，priIndex下标不断向后走

第五步 递归创建左右子树 第六步 返回根结点

则完整代码为：

但是上面完整代码却无法通过全部用例，这里出现问题的是priIndex参数，我们的priIndex参数，预期要求是，一步一步的从0到preorder.length -1 遍历完

但是，在buildTreeChild方法中，priIndex是作为一个局部变量参数出现的，局部变量的生命周期的随着方法结束而结束的，在递归过程中，我们的预期结果根据先序遍历，pi = 1创建F，pi = 2 创建H，然后回归到F，pi再等于 3创建I，但在H回归到F的时候，pi是局部变量，pi由H的2又变回的F的1，导致无法像预期一样到 3 ，创建I

解决方法：将pi创建作为全局变量，全部变量的int类型默认值为0

则完整且正确的代码如下：红色框中的内容是需要将priIndex进行删除的位置

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int priIndex;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) {//1.没有左树 或者 没有右树了if(inbegin > inend) {return null;}//2.创建根结点TreeNode root = new TreeNode(preorder[priIndex]); //根结点为先序遍历数组中的下标为priIndex的元素//3.从中序遍历当中 找到根结点所在的下标int rootIndex = findIndex(inorder, inbegin, inend, preorder[priIndex]);if(-1 == rootIndex) {return null;}//4.先序遍历的下标priIndex不断向后走priIndex++;//5.递归创建左子树 和 右子树//注意！这里必须先递归root.left再递归root.right，因为先序遍历是顺序是根 左 右///创建左子树的时候，inend的值是rootIndex - 1root.left = buildTreeChild(preorder,inorder, inbegin, rootIndex - 1);//创建右子树的时候，inend的值是rootIndex + 1root.right = buildTreeChild(preorder,inorder,rootIndex + 1,inend); //6.返回根结点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;}
}

11. 根据一棵树的后序遍历与中序遍历构造二叉树

力扣链接：106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）

与上体前序遍历百分之九十相似：如下为代码，自行根据注释理解：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int postIndex;public TreeNode buildTree(int[] inorder, int[] postorder) {postIndex = postorder.length - 1;return buildTreeChild(postorder,inorder,0,postorder.length - 1);}private TreeNode buildTreeChild(int[] postorder, int[] inorder, int inbegin, int inend) {//1. 没有左子树 或者 没有右子树if(inbegin > inend) {return null;}//2.创建根结点TreeNode root = new TreeNode(postorder[postIndex]);//3.从中序遍历当中 找到后序遍历中postIndex所在的根结点的下标int rootIndex = findIndex(inorder, inbegin, inend, postorder[postIndex]);postIndex--;//创建左右子树//注意！此处要先创建右树再创建左树//因为后序遍历的顺序是左右根，再根据后序遍历反推二叉树的时候，是从后面遍历后序遍历的即先根再右最后左root.right = buildTreeChild(postorder, inorder, rootIndex + 1, inend);root.left = buildTreeChild(postorder, 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;}
}

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

力扣链接：606. 根据二叉树创建字符串 - 力扣（LeetCode）

给你二叉树的根节点 root ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。

空节点使用一对空括号对 "()" 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

示例1：

将二叉树前序遍历的顺序为： 1 2 4 3

先在字符串中添加1

然后因为2是新的一棵树，所以要加左括号

4同理，也要加左括号，又因为4没有子树了，可以加右括号

此时2也没有了右子树，表明2的子树也遍历完了，可以加右括号

3同理：

总结：1.左边为空 && 右边为空的时候 直接返回

           2. 左边不为空 在字符串添加左括号 然后递归左边 递归完之后 补齐右括号

示例2：

总结：左边不为空，但是右边不为空，此时必须加一对括号

情况汇总：

于是有代码如下：

public String tree2str(TreeNode root) {StringBuilder stringBuilder = new StringBuilder();tree2strChild(root, stringBuilder);return stringBuilder.toString();
}private void tree2strChild(TreeNode root, StringBuilder stringBuilder) {//递归终止条件：若当前结点为null 说明已经遍历到树的末尾了，直接结束即可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;} else {//右子树不为空//此时就是示例二的情况，即左子树为空，右子树不为空，此时不可以忽略左子树的一对括号stringBuilder.append("()");}}//处理右子树//如果右子树不为空if(root.right != null) {//先添加左括号stringBuilder.append("(");//再递归调用方法处理右子树tree2strChild(root.right, stringBuilder);//再补齐右括号stringBuilder.append(")");} else {//右子树为空，当右子树为空的时候，一对括号是可以省略的，直接返回return;}
}

上面的代码就可以跑过力扣所有用例，但是其中if-else嵌套较多，如果思路十分清晰，可以有如下修改：

public String tree2str(TreeNode root) {StringBuilder stringBuilder = new StringBuilder();tree2strChild(root, stringBuilder);return stringBuilder.toString();
}private void tree2strChild(TreeNode root, StringBuilder stringBuilder) {if(root == null) {return;}stringBuilder.append(root.val);if(root.left != null || root.right != null) {//只要左子树或者右子树存在，就需要为左子树部分添加括号。//这是因为即使左子树为空，但右子树不为空时，按照规则也需要用 () 表示空的左子树。stringBuilder.append("(");tree2strChild(root.left, stringBuilder);stringBuilder.append(")");}if(root.right != null) {//这个条件表明只有当右子树存在时，才会处理右子树部分stringBuilder.append("(");tree2strChild(root.right, stringBuilder);stringBuilder.append(")");}
}

13. 二叉树的前序遍历非递归实现

模拟实现递归的实现过程：

public void preOrderNor(TreeNode root) {//空树情况    if(root == null) return;//借助一个栈进行遍历Stcak<TreeNode> stack = new Stack<>();//cur是一个用于指向当前正在处理结点的引用//从根结点开始遍历 cur初始化为传入的根结点TreeNode cur = root;//top用于存储栈顶结点//top是一个临时变量，用于存储栈中弹出的栈顶结点TreeNode top = null;//外层循环//cur != null 标识当前结点不为空，还可以继续向左遍历//!stack.isEmpty() 标识栈中还有元素，即这些结点的右子树还未遍历while(cur != null || !stack.isEmpty()) {//内层循环 前序遍历：根 左 右 所以要尽可能的先访问左子树的结点//该内层循环会从当前结点开始，一直沿着左子树向下遍历，直到左子树为空while(cur != null) {//访问一个结点的时候，需要将其压入栈中//因为内循环只是一直沿着左子树向下遍历，并未处理该结点的右子树，需要先将其保存起来stack.push(cur);System.out.print(cur.val + " ");cur = cur.left;}//内循环结束，代表左子树遍历完，则从栈中弹出栈顶元素top = stack.pop();//处理弹出节点的右子树cur = top.right;}
}

14. 二叉树的中序遍历非递归实现

代码如下：

中序遍历与前序遍历的区别是处理结点的时机有所不同！！！

15. 二叉树的后序遍历非递归实现

public void postOrderNor(TreeNode root) {//处理空树if(root == null) return;//创建栈辅助遍历Staack<TreeNode> stack = new Stack<>();TreeNode cur = root;TreeNode top = null;//用于记录上一个已经访问过的结点//在判断是否可以访问当前栈顶结点时，需要借助prev来确定其右子树是否已经遍历完//外层循环//cur != null 表示当前还有节点需要继续向左遍历//!stack.isEmpty() 表示栈中还有未处理完的节点while(cur != null || !stack.isEmpty()) {//内层循环，先处理左子树while(cur != null) {stack.push(cur);cur = cur.left;}//不能直接弹出栈顶元素，因为后序遍历是左 右 根 还需要处理当前结点的右子树top = stack.peek(); //可以瞄一眼//判断是否可以访问当前栈顶结点//有两种情况可以访问当前栈顶节点：//1. 栈顶节点的右子节点为空，说明没有右子树，可以直接访问该节点。//2. 栈顶节点的右子节点已经被访问过（即等于 prev），说明右子树已经遍历完，可以访问该节点。if(top.right == null || top.right == prev) {//弹出并打印stack.pop();System.out.print(top.val + " ");//更新prev为当前结点prev = top;} else {//若当前右子树还未遍历，则还要再处理右子树cur = top.right;}}
}

完！