作者：学Java的冬瓜
博客主页：☀冬瓜的博客🌙
专栏：【Java 数据结构】
分享：宇宙的最可理解之处在于它是不可理解的，宇宙的最不可理解之处在于它是可理解的。——《乡村教师》
主要内容：二叉树的各类OJ习题，面试题
刷题网站：【牛客网】 【LeetCode官网】

题一：判断二叉树是否完全相同

0、链接：

LeetCode100.相同的树

1、思路：

分析：分为p，q两棵树都空，一棵树空，另一棵树不空。两棵树都不空三种情况。再详细分析

2、代码：

法一：使用 if-else

// 法一：
class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {//1、两棵树都是空树if(p == null && q == null){return true;}//2、结构不同(一棵空，一棵非空)else if((p == null && q != null) || (p != null && q == null)){return false;}//3、都非空else{// 值不同if(p.val != q.val){return false;}// 值相同return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);}}
}

法二：使用 if 排除

// 法二：public boolean isSameTree(TreeNode p, TreeNode q) {//1、两棵树都是空树if(p == null && q == null){return true;}//2、结构不同(一棵空，一棵非空)if((p == null && q != null) || (p != null && q == null)){return false;}//3、都非空// 值不同if(p.val != q.val){return false;}// 值相同return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);}

3、时间复杂度：

// m为p的节点数，n为q的节点数
O(min(m,n)) 
//因为当一棵树遍历完，另一棵树还有节点，
//那就返回false，所以时间复杂度是二者之间的较小值。

题二：判断另一棵树的子树

0、链接：

LeetCode572.另一棵树的子树

1、思路：

分析：
1> 判断两棵树是否相等，相等就可看做subRoot为root子树成立
2> 不等时进入递归循环查找是否符合subRoot是roor的左子树或者右子树。

2、代码：

法一：使用 if-else

// 法一:
class Solution {public boolean isSubtree(TreeNode root, TreeNode subRoot) {//1、判断两棵树相同if(isSameTree(root,subRoot)){return true;}//2、两棵树不同，但root=nullelse if(root == null){return false;}//3、两棵树不同，进入递归判断左子树或者右子树有无和subRoot树相同else{return isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);}}// 判断两棵树是否相同public static boolean isSameTree(TreeNode p, TreeNode q) {//1、两棵树都是空树if(p == null && q == null){return true;}//2、结构不同(一棵空，一棵非空)else if((p == null && q != null) || (p != null && q == null)){return false;}//3、都非空else{// 值不同if(p.val != q.val){return false;}// 值相同return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);}}
}

法二：使用 if 排除

// 法二：
class Solution {public boolean isSubtree(TreeNode root, TreeNode subRoot) {//1、排除在查找过程中root树空了的情况if(root == null){return false;}//2、判断两棵树相同if(isSameTree(root,subRoot)){return true;}//3、进入递归查看每个节点的左子树是否和subRoot相同if(isSubtree(root.left,subRoot)){return true;}//4、进入递归查看每个节点的右子树是否和subRoot相同if(isSubtree(root.right,subRoot)){return true;}return false;}//判断两棵树是否相同public boolean isSameTree(TreeNode p, TreeNode q) {//1、两棵树都是空树if(p == null && q == null){return true;}//2、结构不同(一棵空，一棵非空)if((p == null && q != null) || (p != null && q == null)){return false;}//3、都非空// 值不同if(p.val != q.val){return false;}// 值相同return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);}

3、时间复杂度：

// root有r个节点 subRoot有s个节点
O(r*s)
// 分析：首先root最坏情况要遍历完，
//其次subRoot每次都要和root的根节点开始的树进行比较
//是一个一个节点的比较。所以最终结果为r*s

题三：翻转二叉树

0、链接：

LeetCode226.翻转二叉树

1、思路：

分析：从视觉上看是反转了二叉树每一层的数据。其实就是交换了每一个结点的左右子树

2、代码：

class Solution {public TreeNode invertTree(TreeNode root) {// 1、判断树是否为空，包含最开始时和访问叶子节点后的空if(root == null){return null;}// 2、先把根节点的左子树和右子树交换TreeNode tmp = root.left;root.left = root.right;root.right = tmp;// 3、进入子树递归交换左右子树invertTree(root.left);invertTree(root.right);return root;}
}

3、时间复杂度：

//很明显，最多把每个节点遍历一遍，所以时间复杂度为
O(N)

题四：判断平衡二叉树

0、链接：

LeetCode110.平衡二叉树

1、思路：

分析：
要求这棵树是平衡二叉树，那么必须是这棵树的左右子树都为平衡二叉树。
当root=null时，要么是根节点为空，返回true；要么是叶子节点的子节点为空，说明这个空的父节点们满足isBalance条件，所以也返回true。

2、代码+复杂度：

法一：使用双重递归

// 法一
// 缺陷：时间复杂度为O(N^2)
// 因为求高度的复杂度为O(N)
// 每个节点都求高度，所以约等于O(N^2)
class Solution {public boolean isBalanced(TreeNode root) {// 1、找到空或root本身就是nullif(root == null){return true;}// 2、求该节点左右子树的高度int leftDepth = treeDepth(root.left);int rightDepth = treeDepth(root.right);// 3、当前符合条件的节点，和递归判断左右子树是否平衡// 简单的写法：Matn.abs(leftDepth-rightDepth) <= 1int sub = leftDepth - rightDepth;return sub >= -1 && sub <=1 && isBalanced(root.left) && isBalanced(root.right);}// 求树的高度的方法public int treeDepth(TreeNode root){if(root == null){return 0;}int leftDepth = treeDepth(root.left);int rightDepth = treeDepth(root.right);return leftDepth > rightDepth ? leftDepth+1 : rightDepth+1; }
}

法二：只使用深度递归同时判断平衡

// 法二：强烈推荐
// 时间复杂度只有O(N)
// 思路就是把isBalance递归方法和treeDepth方法递归两个递归变成一个递归。用treeDepth返回值来确定是否平衡和求高度两个任务。
class Solution {public boolean isBalanced(TreeNode root) {// 1、找到空if(root == null){return true;}// 2、非空时，直接把树root传进去，满足平衡就会返回这棵树的深度，否则返回-5return treeDepth(root) >= 0;}// 求树的高度的方法public int treeDepth(TreeNode root){if(root == null){return 0;}int leftDepth = treeDepth(root.left);int rightDepth = treeDepth(root.right);// 注意：相对于法一改变的部分，//要在这里满足leftDepth>=0 && rightDepth>=0，因为会进入递归//且左右高度不能出现等于负数，否则直接return falseif(leftDepth >=0 && rightDepth >= 0 && Math.abs(leftDepth - rightDepth) < 2){return leftDepth > rightDepth ? leftDepth+1 : rightDepth+1; }else{return -5;}}
}

题五：二叉树的层序遍历(非递归)

0、链接：

LeetCode102.二叉树的层序遍历

简单的中序遍历，再打印可以参考这篇C语言博客：
【二叉树基础习题】

1、思路：

说明：
1>先创建一个队列，先把树的根节点入队列
2>然后队列不空就把队头元素取出，再把这个元素的左右子树的非空的根节点入队列
3>最后队列为空时结束

2、代码：

// 注意：值得注意的是，这道OJ题要求用List<List<>>返回。所以要分好节点在哪一层。
// 这里是用计算队列大小的方式，求出当前节点所在层数的元素个数
// 再根据这个元素个数，来界定层数
class Solution {public List<List<Integer>> levelOrder(TreeNode root) {//0、准备返回值List<List<Integer>> lists = new ArrayList<>();// 1、空树if (root == null){return lists;}// 2、非空，先把root树根节点入队列Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()){// 3、计算此时队列里有多少个元素int cnt = queue.size();// 4、把队列里的元素拿出一个，再把这个元素的左右子树的根入队列// 循环直到这一层的元素全从队列拿出来(以cnt=0为结束标志)List<Integer> list = new ArrayList<>();while(cnt > 0){TreeNode out = queue.poll();if(out != null){list.add(out.val);}// 注意：out的左右子树的根不为空，则入队if(out.left != null){queue.offer(out.left);}if(out.right != null){queue.offer(out.right);}// 注意：每出队列一个元素,cnt-1cnt--;}// 5、把一维集合放进二维集合lists.add(list);}// 6、返回类似于二维数组的集合return lists;}
}

题六：判断完全二叉树

1、思路：

说明：这道题不是OJ题，方法和层序遍历非递归的方法非常相似。
思路：
1>按照非递归层序遍历的方式，把所以节点入队列包括null。
2>当遇到null时，退出循环，再判断此时队列中是否有非null的元素，如有非null元素，则不是完全二叉树，返回false。
3>若不断出队，最后队列为空了，也还没返回false，则是完全二叉树，返回true。
注意：在C语言中NULL不能入队，所以这个方法不能用C语言实现。

2、代码：

	public static boolean isCompleteTree(TreeNode root){// 1、空树if (root == null){return false;}// 2、非空,把根节点入队列Queue<TreeNode> qu = new LinkedList<>();qu.offer(root);while (!qu.isEmpty()){// 3、把树的所有节点包括叶子结点的null，//按照层序遍历的方式入队列和出队列，遇到null就退出循环TreeNode cur = qu.poll();if (cur != null){qu.offer(cur.left);qu.offer(cur.right);}else{break;}}// 特别注意：程序进行到这里，必定是从上面循环break出来的，即出队元素遇到了null,所以退出循环//   4、这里要做的就是判断队列剩下的元素中是否有非null元素，有非nill元素则返回false;while(!qu.isEmpty()){if(qu.poll() != null){return false;}}// 5、不断出队，最后队列为空了，也还没返回false，则是完全二叉树，返回true。return true;}

题七：二叉树创建和遍历

0、链接：

牛客网KY11.二叉树遍历

1、代码：

分析法一：

方法一：
定义全局变量，来控制当前的字符位置，但是在多线程中，容易错误，因为线程是不断在切换的。不推荐使用。

法一：利用全局变量i

import java.util.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息public class Main {// 内部类定义树的节点static class TNode{char val;TNode left;TNode right;public TNode(char value){this.val = value;}}// 定义全局变量，来控制当前的字符位置，但是在多线程中，容易错误static int i = 0;public static void main(String[] args) {Scanner in = new Scanner(System.in);String s = in.nextLine();TNode root = createTree(s);inOrder(root);}// 创建二叉树private static TNode createTree(String s){char ch = s.charAt(i++);if(ch == '#'){return null;}TNode node = new TNode(ch);node.left = createTree(s);node.right = createTree(s);return node;}// 中序遍历二叉树private static void inOrder(TNode root){if(root == null){return;}inOrder(root.left);System.out.print(root.val + " ");inOrder(root.right);}
}

分析法二：

方法二：
在main方法中，把字符串放入队列，由队列进行操作。相当于用队列代替了用i遍历字符串的任务。因为队列遍历remove后，不会因为递归而回到上一个字符(如果用局部变量i则会出这个问题)。但是效率比法一低，看情况取舍。
注意：
若需要该题C语言版的，这篇博客步骤讲的更详细一点，可以点以下链接：【牛客.二叉树遍历】-C语言

法二：使用队列解决法一带来的多线程问题

import java.util.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息public class Main {static class TNode{char val;TNode left;TNode right;public TNode(char value){this.val = value;}}// 在main方法中，把字符串放入队列，由队列进行操作public static void main(String[] args) {Scanner in = new Scanner(System.in);String s = in.nextLine();Queue<Character> queue = new LinkedList<>();// 注意：要把字符串变成字符数组才能用foreachfor(char ch : s.toCharArray()){ queue.offer(ch);}TNode root = createTree(queue);inOrder(root);}private static TNode createTree(Queue<Character> queue){char ch = queue.remove();if(ch == '#'){return null;}TNode node = new TNode(ch);node.left = createTree(queue);node.right = createTree(queue);return node;}// 中序遍历private static void inOrder(TNode root){if(root == null){return;}inOrder(root.left);System.out.print(root.val + " ");inOrder(root.right);}
}

题八：二叉树前序遍历

注解：在之前我写过一篇关于二叉树的各种遍历问题的博客，不太懂的小伙伴可以去看看这篇博客
链接：【二叉树的各种遍历问题】

0.链接

LeetCode144.二叉树前序遍历

1.代码

法一：递归

// 法一：递归
class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();preOrder(root,list);return list;}// 递归实现前序遍历，把数据放进list中private static TreeNode preOrder(TreeNode root,List<Integer> list){if(root == null){return null;}list.add(root.val);preOrder(root.left,list);preOrder(root.right,list);return root;}
}

法二：非递归

// 法二：非递归
// 思路：先一直往根节点左走，边打印，边入栈，直到遇到空，再出栈，访问这个出栈的元素的右边。
//只有cur=null 且 栈空，才退出访问。
class Solution {public List<Integer> preorderTraversal(TreeNode root) {TreeNode cur = root;List<Integer> list = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();while(cur!=null || !stack.isEmpty()){if(cur != null){//System.out.print(cur.val + " ");stack.push(cur);list.add(cur.val);cur = cur.left;}else{cur = stack.pop();cur = cur.right;}}return list;}
}

题九：二叉树中序遍历

说明：中序遍历的递归算法和前序遍历算法差不多，这里就不再做过多赘述，有疑问，则看题七中的链接。

0、链接

LeetCode94.二叉树中序遍历

1、代码

// 非递归，方法和前序遍历非递归很像，可以对照学习
class Solution {public List<Integer> inorderTraversal(TreeNode root) {TreeNode cur = root;Stack<TreeNode> stack = new Stack<>();List<Integer> list = new ArrayList<>();while(cur!=null || !stack.isEmpty()){if(cur != null){stack.push(cur);cur = cur.left;}else{cur = stack.pop();list.add(cur.val);cur = cur.right;}}return list;}
}

题十：二叉树后序遍历

0、链接

LeetCode145.二叉树后序遍历

1、代码

class Solution {public List<Integer> postorderTraversal(TreeNode root) {TreeNode cur = root;TreeNode prev = null;Stack<TreeNode> stack = new Stack<>();List<Integer> list = new ArrayList<>();while(cur!=null || !stack.isEmpty()){if(cur!=null){stack.push(cur);cur = cur.left;}else{TreeNode top = stack.peek();if(top.right == null || top.right==prev){cur = stack.pop();list.add(cur.val);// prev 记录前一个已经访问过的节点prev = cur;//重点：这一步很关键，目的是top左孩子为null时//top右孩子为null或者已经访问，则标记以cur为根节点的树已经全部访问cur = null; }else{// top左孩子为空时，如果不满足top右孩子为null，或者有孩子等于prev，就去访问右孩子。cur = top.right;}}}return list;}
}

题十一：二叉树的最近公共祖先

0、链接：

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

1、代码：

法一：利用双栈

原理：
从祖先节点到p或者q节点的深度是确定的，我们用两个栈来分别储存最近祖先节点到p和q的所有节点。
方法：
1> 用pstack储存根节点到p节点的路径，pstack的元素个数就是p的深度。用qstack储存根节点到q节点的路径，qstack的元素个数就是q的深度。
2> 把pstack和qstack中元素个数大的出栈，变成和小的一样的个数，这一步的目的是让搜索来到同一高度。
3> pstack和qstack出栈，然后比较元素是否相等，如果相等就是最近公共祖先，返回该节点；如果都空栈了还不相等就返回null。
4> 要使用后序遍历非递归中栈的使用方法，才能把节点按照p或者q的路径存进栈中，然后遇到p或者要到q时，break跳出循环。

非递归

class Solution {public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root == null) {return null;}//初始准备Stack<TreeNode> ps = new Stack<>();TreeNode pre1 = null;TreeNode cur1 = root;Stack<TreeNode> qs = new Stack<>();TreeNode pre2 = null;TreeNode cur2 = root;// 获取两个节点的路劲while(cur1 != null || !ps.isEmpty()){if(cur1 == p){ps.push(cur1);break;}if(cur1 != null){ps.push(cur1);cur1 = cur1.left;}else{TreeNode top = ps.peek();if(top.right == null || top.right==pre1){cur1 = ps.pop();pre1 = cur1;cur1 = null;}else{cur1 = top.right;}}}while(cur2 != null || !qs.isEmpty()){if(cur2 == q){qs.push(cur2);break;}if(cur2 != null){qs.push(cur2);cur2 = cur2.left;}else{TreeNode top = qs.peek();if(top.right == null || top.right==pre2){cur2 = qs.pop();pre2 = cur2;cur2 = null;}else{cur2 = top.right;}}}// 让两个栈的size和小栈的size相等int psize = ps.size();int qsize = qs.size();if(psize > qsize){int size = psize - qsize;while(size>0){ps.pop();size--;}}else{int size = qsize - psize;while(size>0){qs.pop();size--;}}// 从两个栈中依次取出元素比较，元素相等，就是原始两个节点p和q的公共祖先while (!ps.isEmpty()){TreeNode ptnode = ps.pop();TreeNode qtnode = qs.pop();if(ptnode == qtnode){return ptnode;}}return null;}
}

利用递归(路径函数)

class Solution {public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root == null) {return null;}//初始准备+把数据入栈(利用getPath方法)Stack<TreeNode> ps = new Stack<>();getPath(root,p,ps);Stack<TreeNode> qs = new Stack<>();getPath(root,q,qs);// 让两个栈的size和小栈的size相等int psize = ps.size();int qsize = qs.size();if(psize > qsize){int size = psize - qsize;while(size>0){ps.pop();size--;}}else{int size = qsize - psize;while(size>0){qs.pop();size--;}}// 从两个栈中依次取出元素比较，元素相等，就是原始两个节点p和q的公共祖先while (!ps.isEmpty()){TreeNode ptnode = ps.pop();TreeNode qtnode = qs.pop();if(ptnode == qtnode){return ptnode;}}return null;}// 求根节点到node节点的路径，然后放在栈中private static boolean getPath(TreeNode root,TreeNode node, Stack<TreeNode> stack){// 1、既作为开始判断，有作为递归过程中的判断。if(root == null || node == null){return false;}// 2、在下一步当前节点返回上一层递归前，入栈截至节点stack.push(root);// 3、满足条件，开始递归返回if(root == node){return true;}// 4、在每一层递归里，走到这里说明root!=null && root!=node。所以递归看当前节点的左右子树boolean left = getPath(root.left,node,stack);if(left == true){return true;}boolean right = getPath(root.right,node,stack);if(right == true){return true;}// 5、到这里说明当前节点左右子树中都没找到//    但是当前节点以及入栈，所以先出栈，在返回falsestack.pop();return false;}
}

法二：分情况讨论

分析：
可以大致分为，三种情况。
1> p和q有一个是根节点
2> p和q在根节点的两侧
3> p和q在根节点的一侧
方法：
在递归里，我只需要关心在当前节点的子树当中找没找到p或者q

如果p和q都在根节点的左边，需要两个节点都找到，才能返回公共祖先。
如果p和q在根节点的左右两侧，那就根节点是公共祖先
如果p和q都在根节点右侧，那先找到的那个节点就是公共祖先。

// 法二：分情况讨论
class Solution {// 法二：分情况讨论public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {// 这里代表找到了树的当前方向的尽头// 比如到了叶子节点的左右子树，则返回nullif(root == null || p == null || q == null){return null;}// 第一种情况：p和q有一个在根节点// 还有一个含义是：满足条件时返回这个节点或者qif(root == p || root == q){return root;}// 走到这里，说明 root!=null && p!=null &&q!=null，且p和q均不是根节点。// 进入递归查看左右子树TreeNode leftNode = lowestCommonAncestor(root.left,p,q);TreeNode rightNode = lowestCommonAncestor(root.right,p,q);//第二种：p和q在root两边if(leftNode != null && rightNode != null){return root;}// 第三种：p和q在root的同一侧，且都不在根节点// 重点注意：如果都在root的右侧，那先找到的那一个节点就是最近公告祖先else if (leftNode != null) {return leftNode;} else if (rightNode != null) {return rightNode;}// 注意：这一步是为了防止p和q都在某个节点的右侧时发生错误。//  也可以理解为已经访问的节点没找到p或者q的标记,比如访问到叶子节点，但它不是p或者qelse{return null;}}
}

题十二：二叉搜索树与双向链表

0、链接：

牛客JZ36.二叉搜索树与双向链表

1、思路：

说明：
1> 根据一个convertChild函数，加上prev属性引用(类似于指针传址)，去中序递归实现前驱和后继的改变。
2> 要注意最后的双向链表是中序遍历第一个节点left(前驱)为null（在代码上可以表现出来），中序遍历最后一个节点right(后继)为null，代码上体现不出来，但是这个节点的right本身在树中就是null。
3> 返回值是中序遍历的第一个节点，即节点的left为null的就是返回节点。

2、代码：利用prev引用

// 二叉搜索树与双向链表
public class Solution {public TreeNode Convert(TreeNode pRootOfTree) {if(pRootOfTree == null){return null;}convertChild(pRootOfTree);// 注意：找到二叉搜索树改变为双向链表的头，并返回TreeNode head = pRootOfTree;while(head.left != null){head = head.left;}return head;}// 注意：这个prev要定义在递归之外，相当于指针传地址，改变指针指向private TreeNode prev = null;// 递归方法实现前驱后继的改变private void convertChild(TreeNode pcur){if(pcur == null){return ;}convertChild(pcur.left);pcur.left = prev;if(prev != null){  // 重点注意：排除中序遍历第一个节点执行下面一行代码时，空指针异常prev.right = pcur;}prev = pcur;convertChild(pcur.right);}
}

题十三：从前序和中序遍历序列构造二叉树

0、链接：

LeetCode105.从中序和后序遍历序列构造二叉树

1、思路：

说明：
1> 根据前序和中序构造二叉树，首先要确定的是前序依次从左往右的元素就是根节点，然后在中序中找到根节点位置，从这个位置左右拆分。
2> 因为每一段区间都是相同的操作，所以用递归实现。
3> 因为前序遍历是，根左右。所以我们根据前序和中序创建二叉树也是按照根左右来的，因为需要根据根的顺序创建二叉树。

2、代码：

class Solution {// 根据前序、中序创建二叉树public TreeNode buildTree(int[] preorder, int[] inorder) {return buildTreeChild(preorder,inorder,0,inorder.length-1);}// 递归前序创建二叉树int preindex = 0;  // 重点1：定义全局变量，取消递归的干扰，从而保证从前到后依次遍历preorder数组private TreeNode buildTreeChild(int[] preorder,int[] inorder,int begindex,int Endindex){// 重点2：递归结束条件，也防止数组越界if(begindex > Endindex){return null;}TreeNode root = new TreeNode(preorder[preindex]);// 求前序遍历的节点在中序遍历中作为根节点的位置int rootindex_inorder = findIndex(preorder,inorder);// 重点三：查完前序的节点在中序中根节点位置，再把遍历前序的下标preindex+1preindex++;root.left = buildTreeChild(preorder,inorder,begindex,rootindex_inorder-1);root.right = buildTreeChild(preorder,inorder,rootindex_inorder+1,Endindex);return root;}// 求前序的节点在中序遍历的位置private int findIndex(int[] preorder,int[] inorder){int i = 0;while(i<inorder.length){if(preorder[preindex] == inorder[i]){return i;}i++;}return -1;}
}

题十四：从中序和后序遍历序列构造二叉树

0、链接：

LeetCode106.从中序和后序遍历序列构造二叉树

1、思路：

说明：
1> 大部分思路和上一道题相同
2> 不同点就是这里根节点序列的后序遍历顺序是，左右根。但是我们判断时是把这个序列倒起来看的，从而顺序找出根节点，所以创建二叉树的顺序就是根右左。

2、代码：

class Solution {int postIndex = 0;public TreeNode buildTree(int[] inorder, int[] postorder) {postIndex = postorder.length-1;return buildTreeChild(inorder,postorder,0,inorder.length-1); }private TreeNode buildTreeChild(int[] inorder, int[] postorder, int begindex, int endindex){if(begindex>endindex){return null;}TreeNode root = new TreeNode(postorder[postIndex]);int rootindex_inorder = findIndex(inorder,postorder);postIndex--;root.right = buildTreeChild(inorder,postorder,rootindex_inorder+1,endindex);root.left = buildTreeChild(inorder,postorder,begindex,rootindex_inorder-1);return root;}private int findIndex(int[] inorder, int[] postorder){int i = 0;while(i<inorder.length){if(inorder[i] == postorder[postIndex]){return i;}i++;}return -1;}
}

题十五：根据二叉树创建字符串

0、链接：

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

1、思路：

说明：要把左右子树的递归，放在if-else逻辑里面。分以下几种情况：
判断左边加什么：
1> 左边不为null，加数值 然后进入左递归 再加 “(”
2> 左边为null，右边不为null，加 “()”
3> 左边为null，右边直接返回，不加东西。
判断右边加什么：
1> 右边不为空，加数值 然后进入右递归 再加 “(”
2> 右边为null，直接返回（因为在不为空时已经加上了 “)” )

2、代码：

class Solution {public String tree2str(TreeNode root) {StringBuilder sb = new StringBuilder();treeToStr(root,sb);return sb.toString();}private void treeToStr(TreeNode root, StringBuilder sb){if(root == null){return ;}// 判断左边的情况sb.append(root.val);if(root.left != null){sb.append("(");treeToStr(root.left,sb);sb.append(")");}else{if(root.right == null){return ;}else{sb.append("()");}}// 判断右边的情况if(root.right != null){sb.append("(");treeToStr(root.right,sb);sb.append(")");}else{return ;}}
}