二叉树(链式存储)

文章目录

一、树的基础概念
二、二叉树
- 2.1 概念 + 性质
- 2.2 二叉树的存储
- 2.2 二叉树的基本操作
- - 手动创建一棵二叉树
  - 遍历：前、中、后、层序
  - 获取树中节点的个数
  - 获取叶子节点的个数
  - 获取第K层节点的个数
  - 获取二叉树的高度
  - 检测值为value的元素是否存在
  - 判断一棵树是不是完全二叉树
  - 在root这棵树当中找到node这个节点上的位置
  - 求最大深度
- 2.3 二叉树练习
- - 检查两棵树是否相同
  - 另一棵数的子树
  - 翻转二叉树
  - 是否是平衡二叉树
  - 对称二叉树
  - 二叉树前序非递归遍历实现
  - 二叉树中序非递归遍历实现
  - 二叉树后序非递归遍历实现
  - 二叉树的构建和遍历
  - 二叉树的最近公共祖先
  - 根据二叉树创建字符串
  - 根据一棵树的前序遍历与中序遍历构造二叉树
  - 根据一棵树的中序遍历与后序遍历构造二叉树

一、树的基础概念

（1）树是一种非线性的数据结构。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。同理，作为“树”，它只有一个根节点，且同级节点中没有相交关系
（2）树有三种表示方法，其中最常用的是【孩子兄弟表示法】

在这里插入图片描述

-------重要-------------------------
结点的度：一个结点含有子树的个数称为该结点的度
树的度：一棵树中，所有结点度的最大值称为树的度
叶子结点或终端结点：度为0的结点称为叶子结点
双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点
孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点
根结点：一棵树中，没有双亲结点的结点
结点的层次/深度：从根开始定义起，根为第1层，根的子结点为第2层，以此类推
树的高度或深度：树中结点的最大层次

-------了解-------------------------
非终端结点或分支结点：度不为0的结点
兄弟结点：具有相同父结点的结点互称为兄弟结点
堂兄弟结点：双亲在同一层的结点互为堂兄弟
结点的祖先：从根到该结点所经分支上的所有结点
子孙：以某结点为根的子树中任一结点都称为该结点的子孙
森林：由m（m>=0）棵互不相交的树组成的集合称为森林

二、二叉树

2.1 概念 + 性质

二叉树是指分叉最多为2的树，是树的一种
一个二叉树要么为空，要么就是根节点、右子树、左子树酌情有
二叉树有两种特殊的类别，分别是满二叉树和完全二叉树。其中，满二叉树是一种特殊的完全二叉树
- 满二叉树：一棵二叉树，每层都放满了
- 完全二叉树：没放满，但是是按照顺序放节点

❤️二叉树的性质
在这里插入图片描述

2.2 二叉树的存储

顺序存储：优先级队列（堆）
类似于链表的链式存储：通过一个一个的节点引用起来的，常见的表示方式有孩子表示法和孩子双亲表示法

// 孩子表示法
class Node {int val; // 数据域Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
}
// 孩子双亲表示法
class Node {int val; // 数据域Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树Node parent; // 当前节点的根节点
}

2.2 二叉树的基本操作

手动创建一棵二叉树

public class BinaryTree {static class TreeNode{private int val;private TreeNode left;private TreeNode right;public TreeNode(char val){this.val = val;}}public TreeNode createTree(){TreeNode node1 = new TreeNode('A');TreeNode node2 = new TreeNode('B');TreeNode node3 = new TreeNode('C');TreeNode node4 = new TreeNode('D');TreeNode node5 = new TreeNode('D');TreeNode node6 = new TreeNode('D');node1.left = node2;node1.right = node3;node2.left = node4;node4.right = node5;node3.left = node6;return node1;}
}

遍历：前、中、后、层序

前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点—>根的左子树—>根的右子树

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

//用 List 但是没有用到返回值
List<Integer> ret = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {if(root == null) return ret;//System.out.print(root.val+" ");ret.add(root.val);preorderTraversal(root.left);preorderTraversal(root.right);return ret;
}

//用上了返回值
public List<Integer> preorderTraversal(TreeNode root) {List<Integer> ret = new ArrayList<>();if(root == null) return ret;ret.add(root.val);List<Integer> leftTree = preorderTraversal(root.left);ret.addAll(leftTree);List<Integer> rightTree = preorderTraversal(root.right);ret.addAll(rightTree);return ret;
}

中序遍历(Inorder Traversal)——根的左子树—>根节点—>根的右子树

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

List<Character> ret = new ArrayList<>();
public List<Character> inOrder2(TreeNode root){if (root == null){return ret;}inOrder2(root.left);ret.add(root.val);inOrder2(root.right);return ret;
}

public List<Character> inOrder(TreeNode root){List<Character> ret = new ArrayList<>();if (root == null){return ret;}List<Character> leftTree = inOrder(root.left);ret.addAll(leftTree);ret.add(root.val);List<Character> rightTree = inOrder(root.right);ret.addAll(rightTree);return ret;}

后序遍历(Postorder Traversal)——根的左子树—>根的右子树—>根节点

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

List<Character> ret = new ArrayList<>();
public List<Character> postOrder2(TreeNode root){if (root == null){return ret;}postOrder2(root.left);postOrder2(root.right);ret.add(root.val);return ret;
}

public List<Character> postOrder(TreeNode root){List<Character> ret = new ArrayList<>();if (root == null){return ret;}List<Character> leftTree = postOrder(root.left);ret.addAll(leftTree);List<Character> rightTree = postOrder(root.right);ret.addAll(rightTree);ret.add(root.val);return ret;}

层序遍历
- 此处用非递归的方式更简单，需要创建一个队列来辅助我们，遍历这棵树，root如果不为空就把他放到队列里。如果队列不为空就提出首部元素，然后打印该元素，并把该元素的左右结点放进来
- 如果想要有 List<List< Integer>> 类型的返回值，我们可以通过记录队列的大小来判断当前是在第几层
- 层序遍历变种题：求二叉树的左视图

//无返回值的层序遍历
public void levelOrder(TreeNode root) {Queue<TreeNode> queue = new LinkedList<>();if(root != null) {queue.offer(root);}while (!queue.isEmpty()) {TreeNode top = queue.poll();System.out.print(top.val+" ");if(top.left != null) {queue.offer(top.left);}if(top.right != null) {queue.offer(top.right);}}}

//有返回值的层序遍历
public List<List<Integer>> levelOrder2(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> list = new ArrayList<>();while (size != 0) {TreeNode top = queue.poll();list.add(top.val);if(top.left != null) {queue.offer(top.left);}if(top.right != null) {queue.offer(top.right);}size--;}ret.add(list);}return ret;
}

获取树中节点的个数

// 遍历，只要 root 不为空就可以++public static int usedSize = 0;public int size(TreeNode root) {if(root == null) {return 0;}usedSize++;size(root.left);size(root.right);return usedSize;}//左树结点 + 右树结点 + 1 = 整棵树的结点public int size2(TreeNode root) {if(root == null) {return 0;}return  size2(root.left) + size2(root.right) + 1;}

获取叶子节点的个数

// 遍历，只要 root 不为空就可以++public static int leafSize = 0;public int getLeafNodeCount(TreeNode root) {if(root == null) {return 0;}if(root.left == null && root.right == null) {leafSize++;}getLeafNodeCount(root.left);getLeafNodeCount(root.right);return leafSize;}//左树结点 + 右树结点 + 1 = 整棵树的结点public int getLeafNodeCount2(TreeNode root) {if(root == null) {return 0;}if(root.left == null && root.right == null) {return 1;}return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);}

获取第K层节点的个数

 public int getKLevelNodeCount(TreeNode root, int k) {if(root == null) {return 0;}if(k == 1) {return 1;}return getKLevelNodeCount(root.left,k-1)+ getKLevelNodeCount(root.right,k-1);}

获取二叉树的高度

核心：【左数的高度】和【右树的高度】之间，取最大值
- 【左数的高度】和【右树的高度】怎么求？
方式二有漏洞，会超出时间限制：
- 超出时间限制：代码要求你跑1ms，但实际上跑了2ms，但是代码本身是正确的
- 原因：逻辑中【求左树的高度】和【求右树的高度】都求了两次（判断求谁大谁小一次，算值求了一次），方式一不会出现该问题，因为都只各求了一次
时复：O(n)
- 实际上是遍历的操作，每个结点都遍历到了，如果有n个结点，时间复杂度就是O(n)
时间复杂度 VS 真正的执行时间：两者不一定相等，像该题，方法一和二的时复相同，但方式二的执行时间实际会更长

//方式一public  int getHeight(TreeNode root) {if(root == null) {return 0;}int leftH = getHeight(root.left);int rightH = getHeight(root.right);return (leftH > rightH ? leftH :rightH) + 1;}//方式二public  int getHeight2(TreeNode root) {if(root == null) {return 0;}return (getHeight2(root.left) > getHeight2(root.right) ?getHeight2(root.left) :getHeight2(root.right)) + 1;}

检测值为value的元素是否存在

思路：遍历整个二叉树，如果值为value就返回，遍历方式可以从“前/中/后/层序遍历”中任选其一，此处用的是【前序遍历】

 public TreeNode find(TreeNode root,int val) {if(root == null) return null;if(root.val == val) {return root;} TreeNode leftL = find(root.left,val);if(leftL != null) {return leftL;}TreeNode leftLR = find(root.right,val);if(leftLR != null) {return leftLR;}return null;}

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

思路：创建出一个队列，遍历树并将结点放到队列里，当提出的队首元素为空时，停止遍历操作。然后遍历整个队列，如果队列里没有结点，全是null，说明这是一棵完全二叉树

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

在root这棵树当中找到node这个节点上的位置

public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {if(root == null) {return false;}stack.push(root);if(root == node) {return true;}boolean ret = getPath(root.left,node,stack);if(ret == true) {return true;}boolean ret2 = getPath(root.right,node,stack);if(ret2 == true) {return true;}stack.pop();return false;
}

求最大深度

 public int maxDepth(TreeNode root) {if(root == null) {return 0;}int leftH = maxDepth(root.left);int rightH = maxDepth(root.right);if(leftH >= 0 && rightH >= 0 &&Math.abs(leftH-rightH) <= 1) {return Math.max(leftH,rightH) + 1;}else {return -1;}}

2.3 二叉树练习

检查两棵树是否相同

代码链接
相同的判断：结构相同，里面的value值也相同
思路：
时间复杂度： O(min(m, n))，m和n分别为两棵树的节点个数
- 因为，两棵树如果是不相同的情况下，一定会率先把一棵树遍历完
空间复杂度：O(min(m, n))

 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;}//此时 p 和 q 都不等于空if(p.val != q.val) {return false;}return isSameTree(p.left,q.left)&& isSameTree(p.right,q.right);}

另一棵数的子树

代码链接
关于子树：两颗树一模一样，或者一棵树与另一棵树的一部分一模一样
思路：
（1）判断 root 和 subRoot 是不是两棵相同的树：isSameTree(root,subRoot)

（2）判断root左树的子树是不是subRoot：isSubtree(root.left,subRoot)

（3）判断root左树的子树是不是subRoot：isSubtree(root.right,subRoot)

（4）如果遍历完毕，但是上述的三个条件都不满足，说明你给的根本就不是子树，返回false
为什么要判断 root 是否等于 null：
时间复杂度： O(r * s)，r 和 s 分别为 root 和 subRoot 的节点个数
- 理解：root上的每个点都需要和子树上的判断相不相同

 // 时间复杂度： O(min(m,n))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;}//一定是p 和 q 都不等于空！if(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;}

翻转二叉树

代码链接
思路：

 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;}

是否是平衡二叉树

代码链接
思路：题目要求是所有子树的高度差不能超过1，而不是root的左右树高度差不大于1。那么就是执行遍历操作，每次遍历都计算左右树的高度，如果高度差>1，表示不是平衡二叉树。如果全部遍历完，高度一直都没大于1，那么就是平衡二叉树
方法一：时间复杂度为O(n * n)，n为 root 的结点个数
- 因为每个节点都要去求高度

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

方法二：优化了方法一中，多算了好几次高度的问题，将时间复杂度优化为O(N)
- 在算高度的同时，每次都拿左边高度和右边高度比较一下，如果一旦不平衡了，返回一个负数。相当于本来只是在求root的高度，但是在求的过程中，发现子树已经不符合高度差不超过1的条件了，此时已经不平衡了
- 如果有一个不平衡，会返回-1，后续因为无法通过【left >= 0和right >= 0】的条件，一直返回-1，所以只要最终判断看结果是否大于等于0即可

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

对称二叉树

代码链接

 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);}

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

代码链接
思路：
- 定义一个栈，用栈来模拟递归的过程，先一直取左边的点，只要不为空就放到栈里。当左树的点都放进去后，把栈顶的元素提出来，然后让cur来到该点的右边
- 为什么会有 while (cur != null || !stack.empty())：当走到一个左右结点都无的叶子结点后，把栈顶元素提出来后，该元素的右结点依旧为null，此时如果没有该判断条件，无法让右边的结点也入栈

 public void preOrderNor(TreeNode root) {if(root == null) return;Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while (cur != null || !stack.empty()) {while (cur != null) {stack.push(cur);System.out.print(cur.val + " ");cur = cur.left;}//此时cur == nullTreeNode top = stack.pop();cur = top.right;}}

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

代码链接
思路：先把所有的结点加进来(把根保存起来)，当cur为null才出栈，此处出的栈是最左边的节点

 public void inOrderNor(TreeNode root) {if(root == null) return;Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while (cur != null || !stack.empty()) {while (cur != null) {stack.push(cur);cur = cur.left;}//cur == nullTreeNode top = stack.pop();System.out.print(top.val + " ");cur = top.right;}}

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

代码链接
思路：遍历存结点，但是出线的时候用peek，如果该结点的右边没有结点就打印，如果有结点就根据peek的结果拿到右结点。为避免重复打印和死循环，需要用prev记录下已经被打印过的结点

 public void postOrderNor(TreeNode root) {if(root == null) return;Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;TreeNode prev= null;while (cur != null || !stack.empty()) {while (cur != null) {stack.push(cur);cur = cur.left;}//cur == nullTreeNode top = stack.peek();if(top.right == null || top.right == prev) {System.out.print(top.val+" ");prev = top;//记录下来当前的top已经被打印过了stack.pop();}else {cur = top.right;}}}

二叉树的构建和遍历

代码链接
思路：
- 使用i来遍历字符串，并构造结点：
  - 题目根据前序遍历的方式给了个字符串，我们使用i来遍历的，如果是#，说明不是个结点，不是#说明是结点，需要构造
  - 因为题目给的是前序遍历的字符串，所以我们创建树的时候，也必须根据前序遍历的方式去创建
- 为什么要把i定义在外面：
  - 如果定义在里面，虽然i++了，但是递归之后，执行的逻辑里，i依旧是从0开始
- 越界的情况：
  - i不必要担心越界的情况，因为给的字符串是合理的，是能够构建出一个二叉树的

import java.util.Scanner;
//定义节点
class TreeNode {public char val;public TreeNode left;public TreeNode right;public TreeNode(char val) {this.val = val;}
}public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);while (in.hasNextLine()) {String str = in.nextLine();TreeNode root = createTree(str);inOrder(root);}}public static int i = 0;public static 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 static void inOrder(TreeNode root) {if (root == null) return;inOrder(root.left);System.out.print(root.val + " ");inOrder(root.right);}
}

二叉树的最近公共祖先

代码链接
思路一：让二叉树的每个结点都有一个指向父亲的节点，这样就相当于在求【链表相交结点】。但该思路仅靠二叉树是无法实现的，我们还需要去借助【栈】
- 操作：
  - 我们可以把p和q的路径结点分别存到两个栈上，如果两个长度就不一样，就出掉长度更长的那个栈的结点，直到两个栈长度一样。
  - 当两个栈长度一样时，同时出栈，当出栈的元素一样，说明这个元素就是公共祖先
- 如何把存路径结点：遍历这棵树，只要当前结点不等于p或q，就将其存到栈里，当一个结点左右两边都不包含p或q时，就将其从栈中拿出来，因为它根本不是路径上的值

 public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {if(root == null) return null;Stack<TreeNode> s1 = new Stack<>();getPath(root,p,s1);Stack<TreeNode> s2 = new Stack<>();getPath(root,q,s2);int size1 = s1.size();int size2 = s2.size();if(size1 > size2) {int size = size1 - size2;while (size != 0) {s1.pop();size--;}}else {int size = size2 - size1;while (size != 0) {s2.pop();size--;}}//两个栈当中 的元素 是一样大小的while (!s1.empty() && !s2.empty()) {TreeNode tmp1 = s1.pop();TreeNode tmp2 = s2.pop();if(tmp1 == tmp2) {return tmp1;}}return null;}public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {if(root == null) {return false;}stack.push(root);if(root == node) { //找到这个结点了，返回truereturn true;}//去root左树这边去找node这个结点，找到后放到栈里boolean ret = getPath(root.left,node,stack);if(ret == true) { //此时在子树的左边已经找到了，就不需要再继续找node了，直接返回truereturn true;}boolean ret2 = getPath(root.right,node,stack);if(ret2 == true) {  //此时在左边已经找到了，就不需要再继续找return true; }stack.pop(); //当前这个节点的左右两边都没有我们想要的，出栈+return falsereturn false;}

思路二：

在这里插入图片描述

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null) return null;if(p == root || q == root) {  //情况1return root;}//分别到左右树去找q和p，如果是情况2，那么leftRet和rightRet都会有值//如果是情况3，那么leftRet会是离root最近的值//如果是情况4，那么rightRet会是离root最近的值TreeNode leftRet = lowestCommonAncestor(root.left,p,q);TreeNode rightRet = lowestCommonAncestor(root.right,p,q);if(leftRet != null && rightRet != null) {  return root;  //情况2}else if(leftRet != null) {return leftRet;  //情况3}else {return rightRet;  //情况4}
}

根据二叉树创建字符串

代码链接

class Solution {public String tree2str(TreeNode root) {if (root == null) return null;StringBuilder StringBuilder = new StringBuilder();tree2strChild(root, StringBuilder);return StringBuilder.toString();}private void tree2strChild(TreeNode t, StringBuilder stringBuilder){if (t == null) return;stringBuilder.append(t.val);if (t.left != null){stringBuilder.append("(");tree2strChild(t.left, stringBuilder);stringBuilder.append(")");}else{if (t.right == null){return;}else{stringBuilder.append("()");}}if (t.right != null){stringBuilder.append("(");tree2strChild(t.right, stringBuilder);stringBuilder.append(")");}else{return;}}
}

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

代码链接
思路：
解析：
- 递归的出口：if(inbegin > inend) ，代表该结点的左边和右边都没有结点
- findIndex：在中序遍历中去找关键词key
- 将preIndex提取为成员变量，而不是方法里的局部变量：为了保证preIndex的累加效果(不让递归回去之后，preIndex也回退了)

class Solution {public int preIndex = 0;public TreeNode buildTree(int[] preorder, int[] inorder) {return buildTreeChild(preorder,inorder,0,inorder.length-1);}private TreeNode buildTreeChild(int[] preorder, int[] inorder,int inbegin,int inend) {if(inbegin > inend) {return null;}//先创建根节点TreeNode root = new TreeNode(preorder[preIndex]);//根节点//找到根节点 所在中序遍历中的位置int rootIndex = findIndex(inorder,inbegin,inend,preorder[preIndex]);preIndex++;// 先创建左树 再创建右树   本身是在遍历： 前序遍历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;}
}

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

代码链接
思路：

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);}private TreeNode buildTreeChild(int[] postorder, int[] inorder,int inbegin,int inend) {//递归的出口  不满足这个条件 那么就是没有了左树 或者右树if(inbegin > inend) {return null;}//先创建根节点TreeNode root = new TreeNode(postorder[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;}
}