数据结构与算法 - 二叉树

1. 概述

二叉树是这么一种树状结构:每个节点最多有两个孩子,左孩子和右孩子

完全二叉树:是一种二叉树结构,除了最后一层以外,每一层都必须填满,填充时要遵循从左到右

平衡二叉树:是一种二叉树结构,其中每个节点的左右子树高度相差不超过1

2. 存储

存储方式分为两种:

①定义树结点与左、右孩子引用(TreeNode)

②使用数组,若用0作为树的根节点,索引可以通过以下方式计算

  • 父 = floor((子 - 1) / 2)
  • 左孩子 = 父 * 2 + 1
  • 右孩子 = 父 * 2 + 2

3. 遍历

遍历方式也分为两种:

①广度优先遍历:尽可能先访问距离根节点最近的节点,也称为层序遍历

②深度优先遍历:对于二叉树,可以进一步划分为三种(要深入到叶子节点)

  • pre-order前序遍历:对于每一棵子树,先访问该节点,然后是左子树,最后是右子树
  • in-order中序遍历:对于每一棵子树,先访问左子树,然后是该节点,最后是右子树
  • post-order后续遍历:对于每一棵子树,先访问左子树,然后是右子树,最后是该节点

3.1 广度优先遍历

本轮开始时队列本轮访问节点
[1]1
[2, 3]2
[3, 4]3
[4, 5, 6]4
[5, 6]5
[6, 7, 8]6
[7, 8]7
[8]8
[]

1. 初始化,将根节点加入队列

2. 循环处理队列中每个节点,直至队列为空

3. 每次循环内处理节点后,将它的孩子节点(即下一层节点)加入队列

注意:

  • 以上用队列来实现层序遍历是针对TreeNode这种方式表示的二叉树
  • 对于数组实现的二叉树,则直接遍历数组即可,自然为层序遍历的顺序

3.2 深度优先遍历

栈暂存已处理前序遍历中序遍历
[1]1 ✔️ 左💤 右💤1
[1, 2]2✔️ 左💤 右💤 1✔️ 左💤 右💤2
[1, 2, 4]4✔️ 左✔️ 右✔️ 2✔️ 左💤 右💤 1✔️ 左💤 右💤44
[1, 2]2✔️ 左✔️ 右✔️ 1✔️ 左💤 右💤2
[1]1✔️ 左✔️ 右💤1
[1, 3]3✔️ 左💤 右💤 1✔️ 左✔️ 右💤3
[1, 3, 5]5✔️ 左✔️ 右✔️ 3✔️ 左💤 右💤 1✔️ 左✔️ 右💤55
[1, 3]3✔️ 左✔️ 右💤 1✔️ 左✔️ 右💤3
[1, 3, 6]6✔️ 左✔️ 右✔️ 3✔️ 左✔️ 右💤 1✔️ 左✔️ 右💤66
[1, 3]3✔️ 左✔️ 右✔️ 1✔️ 左✔️ 右💤
[1]1✔️ 左✔️ 右✔️
[]

3.2.1 递归实现

/*** <h3>前序遍历</h3>* @param node 节点*/
static void preOrder(TreeNode node) {if (node == null) {return;}System.out.print(node.val + "\t"); // 值preOrder(node.left); // 左preOrder(node.right); // 右
}/*** <h3>中序遍历</h3>* @param node 节点*/
static void inOrder(TreeNode node) {if (node == null) {return;}inOrder(node.left); // 左System.out.print(node.val + "\t"); // 值inOrder(node.right); // 右
}/*** <h3>后序遍历</h3>* @param node 节点*/
static void postOrder(TreeNode node) {if (node == null) {return;}postOrder(node.left); // 左postOrder(node.right); // 右System.out.print(node.val + "\t"); // 值
}

3.2.2 非递归实现

前序遍历

LinkedListStack<TreeNode> stack = new LinkedListStack<>();  // 此处的LinkedListStack为自己实现的
TreeNode curr = root;while (!stack.isEmpty() || curr != null) {if (curr != null) {stack.push(curr);System.out.println(curr);curr = curr.left;} else {TreeNode pop = stack.pop();curr = pop.right;}}

中序遍历

LinkedListStack<TreeNode> stack = new LinkedListStack<>();
TreeNode curr = root;while (!stack.isEmpty() || curr != null) {if (curr != null) {stack.push(curr);curr = curr.left;} else {TreeNode pop = stack.pop();System.out.println(pop);curr = pop.right;}
}

后序遍历

LinkedListStack<TreeNode> stack = new LinkedListStack<>();
TreeNode curr = root;
TreeNode pop = null;while (!stack.isEmpty() || curr != null) {if (curr != null) {stack.push(curr);curr = curr.left;} else {TreeNode peek = stack.peek();if (peek.right == null || peek.right == pop) {pop = stack.pop();System.out.println(pop);} else {curr = peek.right;}}
}

对于后序遍历,向后走时,需要处理完右子树才能pop出栈。如何直到右子树处理完成呢?

①如果栈顶元素的 right == null ,表示没啥可处理的,可以出栈

②如果栈顶元素的 right != null 

  • 那么使用lastPop记录最近出栈的节点,即表示从这个节点向回走
  • 如果栈顶元素 right == lastPop,此时应当出栈

对于前、中两种遍历,实际以上代码从右子树向回走时,并未走完全程(stack提前出栈了),而后序遍历以上代码是走完全程了。

统一写法(依据后序遍历修改)

LinkedList<TreeNode> stack = new LinkedList<>();TreeNode curr = root; // 代表当前节点
TreeNode pop = null; // 最近一次弹栈的元素
while (curr != null || !stack.isEmpty()) {if (curr != null) {colorPrintln("前: " + curr.val, 31);stack.push(curr); // 压入栈,为了记住回来的路curr = curr.left;} else {TreeNode peek = stack.peek();// 右子树可以不处理, 对中序来说, 要在右子树处理之前打印if (peek.right == null) {colorPrintln("中: " + peek.val, 36);pop = stack.pop();colorPrintln("后: " + pop.val, 34);}// 右子树处理完成, 对中序来说, 无需打印else if (peek.right == pop) {pop = stack.pop();colorPrintln("后: " + pop.val, 34);}// 右子树待处理, 对中序来说, 要在右子树处理之前打印else {colorPrintln("中: " + peek.val, 36);curr = peek.right;}}
}public static void colorPrintln(String origin, int color) {System.out.printf("\033[%dm%s\033[0m%n", color, origin);
}

一张图演示三种遍历

  • 红色:前序遍历
  • 绿色:中序遍历
  • 蓝色:后序遍历

4. 习题

4.1 前序遍历二叉树

给你二叉树的根节点 root ,返回它节点值的 前序 遍历。

示例 1:

输入:root = [1,null,2,3]
输出:[1,2,3]

示例 2:

输入:root = []
输出:[]

示例 3:

输入:root = [1]
输出:[1]

示例 4:

输入:root = [1,2]
输出:[1,2]

示例 5:

输入:root = [1,null,2]
输出:[1,2]

提示:

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

进阶:递归算法很简单,你可以通过迭代算法完成吗?

解法一:递归

/*** 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<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();preorderHelper(root, result);return result;}private void preorderHelper(TreeNode root, List<Integer> result) {if (root == null) {return;}result.add(root.val);preorderHelper(root.left, result);preorderHelper(root.right, result);}
}

解法二:迭代

/*** 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<Integer> preorderTraversal(TreeNode root) {LinkedList<TreeNode> stack = new LinkedList<>();List<Integer> result = new ArrayList<>();TreeNode curr = root;while (!stack.isEmpty() || curr != null) {if (curr != null) {stack.push(curr);result.add(curr.val);curr = curr.left;} else {TreeNode pop = stack.pop();curr = pop.right;}}return result;}
}

解法三:莫里斯遍历(Morris Traversal)

①莫里斯遍历的核心思想是通过利用树的空指针链接来避免使用栈

②对于每个节点,如果它的左子树为空,则访问当前节点并移动到右子树

③如果左子树不为空,找到当前节点的前驱节点(即左子树中最右的节点),检查它的右指针

  • 如果它的右指针为空,则将其指向当前节点,并返回当前节点
  • 如果它的右指针已经指向当前节点,说明左子树已经遍历结束,将右指针恢复为null,并移动到右子树。

时间复杂度:O(n);空间复杂度:O(1)

/*** 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<Integer> preorderTraversal(TreeNode root) {  List<Integer> result = new ArrayList<>();  TreeNode curr = root;  while (curr != null) {  if (curr.left == null) {  // 访问当前节点  result.add(curr.val);  curr = curr.right; // 移动到右子树  } else {  // 找到当前节点的前驱节点  TreeNode pred = curr.left;  while (pred.right != null && pred.right != curr) {  pred = pred.right;  }  // 建立链接  if (pred.right == null) {  pred.right = curr; // 建立临时连接  result.add(curr.val); // 访问当前节点  curr = curr.left; // 移动到左子树  } else {  // 恢复树结构  pred.right = null;  curr = curr.right; // 移动到右子树  }  }  }  return result;  }  
}  

4.2 中序遍历二叉树

给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。

示例 1:

输入:root = [1,null,2,3]
输出:[1,3,2]

示例 2:

输入:root = []
输出:[]

示例 3:

输入:root = [1]
输出:[1]

提示:

  • 树中节点数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

解法一:递归

/*** 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<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();inorderHelper(root, result);return result;}private void inorderHelper(TreeNode root, List<Integer> result) {if (root == null) {return;}inorderHelper(root.left, result);result.add(root.val);inorderHelper(root.right, result);}
}

解法二:迭代

/*** 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<Integer> inorderTraversal(TreeNode root) {LinkedList<TreeNode> stack = new LinkedList<>();List<Integer> result = new ArrayList<>();TreeNode curr = root;while (!stack.isEmpty() || curr != null) {if (curr != null) {stack.push(curr);curr = curr.left;} else {TreeNode pop = stack.pop();result.add(pop.val);curr = pop.right;}}return result;}
}

解法三:莫里斯算法

①莫里斯遍历的核心思想是通过利用树的空指针链接来避免使用栈

②对于每个节点,如果它的左子树为空,则访问当前节点并移动到右子树

③如果左子树不为空,找到当前节点的前驱节点(即左子树中最右的节点),检查它的右指针

  • 如果它的右指针为空,则将其指向当前节点,并返回当前节点
  • 如果它的右指针已经指向当前节点,说明左子树已经遍历结束,将右指针恢复为null,并移动到右子树。
/*** 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<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();TreeNode curr = root;while (curr != null) {if (curr.left == null) { // 左子树为空// 访问当前节点result.add(curr.val);// 移动到右子树curr = curr.right;} else {// 找到当前节点的前驱节点TreeNode pred = curr.left;while (pred.right != null && pred.right != curr) {pred = pred.right;}// 建立链接if (pred.right == null) {// 建立临时链接pred.right = curr;// 移动到左子树curr = curr.left;} else {// 恢复树结构pred.right = null;// 访问当前节点result.add(curr.val);// 移动到右子树curr = curr.right;}}}return result;}
}

4.3 后序遍历二叉树

给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历 

示例 1:

输入:root = [1,null,2,3]
输出:[3,2,1]

示例 2:

输入:root = []
输出:[]

示例 3:

输入:root = [1]
输出:[1]

提示:

  • 树中节点的数目在范围 [0, 100] 内
  • -100 <= Node.val <= 100

进阶:递归算法很简单,你可以通过迭代算法完成吗?

解法一:递归

/*** 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<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();postOrderHelper(root, result);return result;}private void postOrderHelper(TreeNode root, List<Integer> result) {if (root == null) {return;}postOrderHelper(root.left, result);postOrderHelper(root.right, result);result.add(root.val);}
}

解法二:迭代

/*** 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<Integer> postorderTraversal(TreeNode root) {LinkedList<TreeNode> stack = new LinkedList<>();List<Integer> result = new ArrayList<>();TreeNode curr = root;TreeNode pop = null;while (!stack.isEmpty() || curr != null) {if (curr != null) {stack.push(curr);curr = curr.left;} else {TreeNode peek = stack.peek();if (peek.right == null || peek.right == pop) {pop = stack.pop();result.add(pop.val);} else {curr = peek.right;}}}return result;}
}

4.4 对称二叉树

给你一个二叉树的根节点 root , 检查它是否轴对称。

示例 1:

输入:root = [1,2,2,3,4,4,3]
输出:true

示例 2:

输入:root = [1,2,2,null,3,null,3]
输出:false

提示:

  • 树中节点数目在范围 [1, 1000] 内
  • -100 <= Node.val <= 100

进阶:你可以运用递归和迭代两种方法解决这个问题吗?

解法一:递归

/*** 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 boolean isSymmetric(TreeNode root) {if(root == null) {return true;}return dfs(root.left, root.right);}private boolean dfs(TreeNode left, TreeNode right) {if(left == null && right == null) {return true;} if(left == null || right == null) {return false;}return (left.val == right.val) && dfs(left.left, right.right) && dfs(left.right, right.left);}
}

解法二:迭代

/*** 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 boolean isSymmetric(TreeNode root) {if (root == null) {return true;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root.left);queue.offer(root.right);while (!queue.isEmpty()) {TreeNode leftNode = queue.poll();TreeNode rightNode = queue.poll();if (leftNode == null && rightNode == null) {  // 左右两个子树为空continue;}if (leftNode == null || rightNode == null) {  // 两边只有一个子树为空return false;}if (leftNode.val != rightNode.val) {return false;}queue.offer(leftNode.left);queue.offer(rightNode.right);queue.offer(leftNode.right);queue.offer(rightNode.left);}return true;}
}

4.5 二叉树最大深度

给定一个二叉树 root ,返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1:

输入:root = [3,9,20,null,null,15,7]
输出:3

示例 2:

输入:root = [1,null,2]
输出:2

提示:

  • 树中节点的数量在 [0, 10^4] 区间内。
  • -100 <= Node.val <= 100

解法一:递归

/*** 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 maxDepth(TreeNode root) {if (root == null) {return 0;}return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;}
}

解法二:

/*** 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 maxDepth(TreeNode root) {if (root == null) {return 0;}Stack<Pair<TreeNode, Integer>> stack = new Stack<>();stack.push(new Pair<>(root, 1));int maxDepth = 0;while (!stack.isEmpty()) {Pair<TreeNode, Integer> current = stack.pop();TreeNode node = current.getKey();int depth = current.getValue();maxDepth = Math.max(depth, maxDepth);if (node.left != null) {stack.push(new Pair<>(node.left, depth + 1));}if (node.right != null) {stack.push(new Pair<>(node.right, depth + 1));}}return maxDepth;}
}

解法三:使用二叉树的非递归后序遍历,栈的最大高度即为最大深度

/*** 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 maxDepth(TreeNode root) {TreeNode curr = root;TreeNode pop = null;LinkedList<TreeNode> stack = new LinkedList<>();int max = 0; // 栈的最大高度while(curr != null || !stack.isEmpty()) {if(curr != null) {stack.push(curr);max = Integer.max(stack.size(), max);curr = curr.left;} else {TreeNode peek = stack.peek();if(peek.right == null || peek.right == pop) {pop = stack.pop();} else {curr = peek.right;}}}return max;}
}

解法四:二叉树的层序遍历,层数即最大深度

/*** 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 maxDepth(TreeNode root) {if (root == null) {return 0;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);int depth = 0;while (!queue.isEmpty()) {int size = queue.size();for (int i = 0; i < size; i++) {TreeNode poll = queue.poll();if (poll.left != null) {queue.offer(poll.left);}if (poll.right != null) {queue.offer(poll.right);}}depth++;}return depth;}
}

4.6 二叉树最小深度

给定一个二叉树,找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明:叶子节点是指没有子节点的节点。

示例 1:

输入:root = [3,9,20,null,null,15,7]
输出:2

示例 2:

输入:root = [2,null,3,null,4,null,5,null,6]
输出:5

提示:

  • 树中节点数的范围在 [0, 10^5] 内
  • -1000 <= Node.val <= 1000

解法一:层序遍历。遇到第一个叶子节点所在层数即为最小深度

/*** 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 minDepth(TreeNode root) {if (root == null) {return 0;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);int depth = 1;while (!queue.isEmpty()) {int size = queue.size();for (int i = 0; i < size; i++) {TreeNode node = queue.poll();if (node.left == null && node.right == null) {return depth;}if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}depth++;}return depth;}
}

解法二:后序遍历

相较于求最大深度,应当考虑:

  • 当右子树为null,应当返回左子树深度加一
  • 当左子树为null,应当返回右子树深度加一
/*** 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 minDepth(TreeNode node) {if (node == null) {return 0;}int d1 = minDepth(node.left);int d2 = minDepth(node.right);if (d1 == 0 || d2 == 0) {return d1 + d2 + 1;}return Integer.min(d1, d2) + 1;}
}

4.7 翻转二叉树

给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。

示例 1:

输入:root = [4,2,7,1,3,6,9]
输出:[4,7,2,9,6,3,1]

示例 2:

输入:root = [2,1,3]
输出:[2,3,1]

示例 3:

输入:root = []
输出:[]

提示:

  • 树中节点数目范围在 [0, 100] 内
  • -100 <= Node.val <= 100

解法一:递归

/*** 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 TreeNode invertTree(TreeNode root) {reverse(root);return root;}private void reverse(TreeNode node) {if(node == null) {return;}TreeNode t = node.left;node.left = node.right;node.right = t;reverse(node.left);reverse(node.right);}
}

/*** 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 TreeNode invertTree(TreeNode root) {if(root == null) {return null;}// 递归翻转左右子树TreeNode left = invertTree(root.left);TreeNode right = invertTree(root.right);// 交换左右子树// TreeNode t = root.left;root.left = root.right;root.right = left;return root;}
}

4.8 后缀表达式转二叉树

  • 遇到运算符,则出栈两次,将出栈元素与当前节点建立父子关系,当前节点入栈
  • 遇到数字则入栈
    public TreeNode constructExpressionTree(String[] tokens) {LinkedList<TreeNode> stack = new LinkedList<>();for (String token : tokens) {switch (token) {// 遇到运算符,出栈两次,与当前节点建立父子关系,将当前节点入栈case "+", "-", "*", "/" -> {TreeNode right = stack.pop();TreeNode left = stack.pop();TreeNode parent = new TreeNode(Integer.parseInt(token));parent.left = left;parent.right = right;stack.push(parent);}default -> {  // 遇到数字入栈stack.push(new TreeNode(Integer.parseInt(token)));}}}return stack.peek();}

4.9 根据前序与中序遍历结果构造二叉树

给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

提示:

  • 1 <= preorder.length <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • preorder 和 inorder 均 无重复 元素
  • inorder 均出现在 preorder
  • preorder 保证 为二叉树的前序遍历序列
  • inorder 保证 为二叉树的中序遍历序列

解法一:

  • 先通过前序遍历结果定位根节点
  • 再结合中序遍历结果切分左右子树
/*** 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 TreeNode buildTree(int[] preorder, int[] inorder) {Map<Integer, Integer> indexMap = new HashMap<>();for (int i = 0; i < inorder.length; i++) {indexMap.put(inorder[i], i);}return buildTreeHelper(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1, indexMap);}private TreeNode buildTreeHelper(int[] preorder, int[] inorder, int preStart, int preEnd, int inStart, int inEnd,Map<Integer, Integer> indexMap) {if (preStart > preEnd || inStart > inEnd) {return null;}int rootVal = preorder[preStart]; // 根节点的位置TreeNode root = new TreeNode(rootVal);int inIndex = indexMap.get(rootVal);int leftSubtreeSize = inIndex - inStart; // 左子树root.left = buildTreeHelper(preorder, inorder, preStart + 1, preStart + leftSubtreeSize, inStart, inIndex - 1,indexMap);root.right = buildTreeHelper(preorder, inorder, preStart + leftSubtreeSize + 1, preEnd, inIndex + 1, inEnd,indexMap);return root;}
}

4.10 根据中序与后序遍历结果构造二叉树

解法一:

  • 先通过后序遍历结果定位根节点
  • 再结合中序遍历结果划分左右子树
/*** 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 TreeNode buildTree(int[] inorder, int[] postorder) {Map<Integer, Integer> indexMap = new HashMap<>();for (int i = 0; i < inorder.length; i++) {indexMap.put(inorder[i], i);}return buildTreeHelper(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1, indexMap);}private TreeNode buildTreeHelper(int[] inorder, int[] postorder, int inStart, int inEnd, int postStart, int postEnd,Map<Integer, Integer> indexMap) {if (inStart > inEnd || postStart > postEnd) {return null;}int rootVal = postorder[postEnd]; // 根节点的位置TreeNode root = new TreeNode(rootVal);int inIndex = indexMap.get(rootVal);int rightSubtreeSize = inEnd - inIndex; // 右子树root.left = buildTreeHelper(inorder, postorder, inStart, inIndex - 1, postStart, postEnd - rightSubtreeSize - 1,indexMap);root.right = buildTreeHelper(inorder, postorder, inIndex + 1, inEnd, postEnd - rightSubtreeSize, postEnd - 1,indexMap);return root;}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/391810.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Pip 使用报错及解决

pip install 是Python 包管理器命令&#xff0c;常用参数&#xff1a; -r&#xff1a;从一个需求文件中安装所有的包。-U 或 --upgrade&#xff1a;升级一个已经安装的包到最新版本。-I 或 --ignore-installed&#xff1a;即使包已经安装&#xff0c;也重新安装。--no-cache-d…

要想赚钱,AI模型该大该小?贾扬清:论AI模型经济学的技巧

卖模型就像感恩节卖火鸡&#xff0c;快才能赚钱。 最近的AI社区&#xff0c;关于模型规模的讨论有些活跃。 一方面&#xff0c;此前在大模型开发奉为“圣经”的Scaling Law&#xff0c;似乎正在褪去光环。去年大家还在猜测GPT-5的规模“可能会大到想不到”&#xff0c;现在这…

推荐一款界面优雅、功能强大的 .NET + Vue 权限管理系统

目录 前言 项目简介 项目特点 项目预览 项目演示 1、系统登录 2、系统首页 3、系统页面 4、插件示例 5、移动端 项目地址 总结 前言 今天推荐一款用 .NET 和 Vue3 实现的开源权限管理系统。它的界面清爽干净&#xff0c;功能强大&#xff0c;还具备灵活的角色权限分配…

19 注意力机制

目录 1.注意力机制从心理学的角度出发注意力机制非参注意力池化层Nadaraya-Watson 核回归:总结注意力汇聚:Nadaraya-Watson 核 代码实现非参数注意力汇聚(非参数注意力池化)注意力权重参数注意力汇聚(参数注意力池化)2.注意力分数如何将 key 和 value 拓展到更高的维度掩…

Bug 解决 | 后端项目无法正常启动,或依赖服务连接失败

目录 1、版本问题 2、依赖项问题 明明拷贝的代码&#xff0c;为什么别人行&#xff0c;我启动就报错&#xff1f; 这篇文章我就理一下最最常见的项目启动报错的两种原因&#xff01; 1、版本问题 比如明明项目的 Java 版本是 8&#xff0c;你非得拿 5 跑&#xff1f;那不是…

C++基础知识(入门章)

绪论 历经千辛万苦&#xff0c;我们终于来到了一个全新的板块---C。本期的内容主要是关于C的一些基础知识的初步了解。让我们一起努力&#xff0c;克服编程路上的艰难险阻&#xff0c;迎接属于自己成功的彼岸~ C的发展历史 1979年 C的起源可以追溯到1979年&#xff0c;当时B…

基于K210智能人脸识别+车牌识别系统(完整工程资料源码)

运行效果&#xff1a; 基于K210的智能人脸与车牌识别系统工程 目录&#xff1a; 运行效果&#xff1a; 目录&#xff1a; 前言&#xff1a; 一、国内外研究现状与发展趋势 二、相关技术基础 2.1 人脸识别技术 2.2 车牌识别技术 三、智能小区门禁系统设计 3.1 系统设计方案 3.2 …

卓越运营必备神器:规划复杂项目、使用标准的项目模板,看Minitab Workspace!

可确保过程与产品卓越性的可视化工具 您是否知道Minitab Workspace是专门为Minitab统计软件配套而设计的&#xff1f; 您和您的团队或许会面临以下相关问题: 1) 在规划复杂项目上存在困难&#xff0c;如业务优化项目; 2) 因完成工作需要而使用多种未知品牌的产品; 3) 缺乏…

一款好用的开源网站内容管理系统

今天给大家介绍的是一款开源网站内容管理系统&#xff08;灵活、易用&#xff0c;性能良好、运行稳定&#xff0c;轻松管理建设网站&#xff09; 官网&#xff1a;https://www.ujcms.com/ 介绍 客户端兼容Edge&#xff08;Chromium版&#xff09;、谷歌浏览器&#xff08;Chro…

AI称重收银一体秤

系统介绍 专门为零售行业的连锁店量身打造的收银系统&#xff0c;适用于常规超市、生鲜超市、水果店、便利店、零食专卖店、服装店、母婴用品、农贸市场等类型的门店使用。同时线上线下数据打通&#xff0c;线下收银的数据与小程序私域商城中的数据完全同步&#xff0c;如商品…

MMC和eMMC的区别

MMC 和 eMMC 的区别 1. MMC MMC&#xff08;MultiMediaCard&#xff09;是一种接口协议&#xff0c;定义了符合这一接口的内存器&#xff0c;称为 MMC 储存体或 MMC 卡。它是一种非易失性存储器件&#xff0c;广泛应用于消费类电子产品中。 1.1 外观及引脚定义 MMC卡共有七个…

LLM之本地部署GraphRAG(GLM-4+Xinference的embedding模型)(附带ollma部署方式)

前言 有空再写 微软开源的GraphRAG默认是使用openai的接口的&#xff08;GPT的接口那是要money的&#xff09;&#xff0c;于是就研究了如何使用开源模型本地部署。 源码地址&#xff1a;https://github.com/microsoft/graphrag 操作文档&#xff1a;https://microsoft.git…

nextjs 实现TodoList网页应用案例

参考&#xff1a; https://nextjs.org/ Next.js 是用于网络的一种 React 框架。一些世界上最大的公司在使用它&#xff0c;它能够借助 React 组件的力量让您创建高质量的网络应用程序。 1、创建项目&#xff1a; 另外注意&#xff1a;pages与app路由存在冲突&#xff0c;如果有…

Jenkins未授权访问漏洞 *

漏洞复现 步骤一&#xff1a;使用以下fofa语法进行产品搜索.... port"8080" && app"JENKINS" && title"Dashboard [Jenkins]" 步骤二&#xff1a;在打开的URL中...点击Manage Jenkins --> Scritp Console在执行以下命令..…

leetcode数论(​3044. 出现频率最高的质数)

前言 经过前期的基础训练以及部分实战练习&#xff0c;粗略掌握了各种题型的解题思路。现阶段开始专项练习。 描述 给你一个大小为 m x n 、下标从 0 开始的二维矩阵 mat 。在每个单元格&#xff0c;你可以按以下方式生成数字&#xff1a; 最多有 8 条路径可以选择&#xff1…

通俗易懂!495页看漫画学Python入门教程(全彩版)Git首发破万Star

前言 在编程的世界里&#xff0c;Python无疑是一颗璀璨的明星。从最初作为打发圣诞节闲暇时间的项目&#xff0c;到如今成为最受欢迎的程序设计语言之一&#xff0c;Python以其简洁、易学、强大的特点吸引了无数编程爱好者。然而&#xff0c;对于初学者来说&#xff0c;编程的…

【redis 第八篇章】链表结构

一、数组和链表 1、数组 数组会在内存中开辟一块连续的空间存储数据&#xff0c;这种存储方式有利也有弊端。当获取数据的时候&#xff0c;直接通过下标值就可以获取到对应的元素&#xff0c;时间复杂度为 O(1)。但是如果新增或者删除数据会移动大量的数据&#xff0c;时间复…

范伟:大叔这句是咱俩合唱的,赵本山:我唱不上去!——小品《门神》(下)的台词与解说

范伟&#xff1a;大叔这句是咱俩合唱的&#xff0c;赵本山&#xff1a;我唱不上去&#xff01; ——小品《门神》&#xff08;下&#xff09;的台词与解说 &#xff08;接上&#xff09; 范伟&#xff1a;大叔快快快走 赵本山&#xff1a;干啥 范伟&#xff1a;上咱家过年…

苹果手机锁屏怎么设置?3个技巧,教你快速设置

在科技与创意交织的时代&#xff0c;苹果手机以其简约而不失优雅的设计&#xff0c;成为了我们日常生活中不可或缺的一部分。而作为手机的【第一印象】&#xff0c;锁屏界面更是彰显用户个性的关键所在。那么&#xff0c;苹果手机锁屏怎么设置呢&#xff1f;接下来&#xff0c;…

AI生成PPT?三款工具让总结更轻松

哎呀&#xff0c;职场新人们&#xff0c;你们是不是也跟我一样&#xff0c;刚开始做PPT的时候&#xff0c;感觉像是走进了一个大迷宫&#xff0c;脑袋里装满了想法&#xff0c;但就是不知道怎么把它们变成一页页漂亮的幻灯片&#xff1f;别急&#xff0c;今天咱们就来聊聊三个超…