二叉树(链式存储)
一、树的基础概念
（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 == null
TreeNode 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 == null
TreeNode 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 == null
TreeNode 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不必要担心越界的情况，因为给的字符串是合理的，是能够构建出一个二叉树的
- 使用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) { //找到这个结点了，返回true
return true;
}
//去root左树这边去找node这个结点，找到后放到栈里
boolean ret = getPath(root.left,node,stack);
if(ret == true) { //此时在子树的左边已经找到了，就不需要再继续找node了，直接返回true
return true;
}
boolean ret2 = getPath(root.right,node,stack);
if(ret2 == true) { //此时在左边已经找到了，就不需要再继续找
return true;
}
stack.pop(); //当前这个节点的左右两边都没有我们想要的，出栈+return false
return false;
}
- 思路二：
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) return null;
if(p == root || q == root) { //情况1
return 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;
}
}
原文地址：https://blog.csdn.net/wuweixiaoyue/article/details/142437940
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！