上接：【题解】—— LeetCode一周小结7
19.N 叉树的后序遍历
题目链接：590. N 叉树的后序遍历
给定一个 n 叉树的根节点 root ，返回 其节点值的 后序遍历 。
n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。
示例 1：
输入：root = [1,null,3,2,4,null,5,6]
输出：[5,6,3,2,4,1]
示例 2：
输入：root =
[1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[2,6,14,11,7,3,12,8,4,13,9,10,5,1]
提示：
节点总数在范围 [0, 104] 内
0 <= Node.val <= 104
n 叉树的高度小于或等于 1000
题解：
方法：递归
/* // Definition for a Node. class Node { public int val; public List<Node> children; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, List<Node> _children) { val = _val; children = _children; } }; */ class Solution { List<Integer> ans = new ArrayList<>(); public List<Integer> postorder(Node root) { dfs(root); return ans; } void dfs(Node root) { if (root == null) return; for (Node node : root.children) dfs(node); ans.add(root.val); } }
方法：非递归
/* // Definition for a Node. class Node { public int val; public List<Node> children; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, List<Node> _children) { val = _val; children = _children; } }; */ class Solution { public List<Integer> postorder(Node root) { List<Integer> ans = new ArrayList<>(); Deque<Object[]> d = new ArrayDeque<>(); d.addLast(new Object[]{0, root}); while (!d.isEmpty()) { Object[] poll = d.pollLast(); Integer cnt = (Integer)poll[0]; Node t = (Node)poll[1]; if (t == null) continue; if (cnt == t.children.size()) ans.add(t.val); if (cnt < t.children.size()) { d.addLast(new Object[]{cnt + 1, t}); d.addLast(new Object[]{0, t.children.get(cnt)}); } } return ans; } }
20.从前序与中序遍历序列构造二叉树
题目链接：105. 从前序与中序遍历序列构造二叉树
给定两个整数数组 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 保证 为二叉树的中序遍历序列
题解：
方法：递归
变量 pre 保存当前要构造的树的 root
变量 in 保存 inorder 数组中可以成为 root 的数字们的开头那个
对于当前要构造的树，有一个停止点 stop ，inorder 数组中第 in 项到第 stop 项是要构造的树的节点值们
每次递归调用，都会确定出一个停止点，它告诉了子
调用在哪里停止，把自己的根节点值作为左子树调用的停止点，自己的（父调用给下来的）停止点作为右子树的停止点
/** * 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 { private int in = 0; private int pre = 0; public TreeNode buildTree(int[] preorder, int[] inorder) { return build(preorder, inorder, Integer.MIN_VALUE); } private TreeNode build(int[] preorder, int[] inorder, int stop) { if (pre == preorder.length) return null; // pre走到preorder末尾 if (inorder[in] == stop) { // in指针走到了停止点 in++; // stop点废弃了，in推进一位 return null; } TreeNode node = new TreeNode(preorder[pre++]); node.left = build(preorder, inorder, node.val); // 左子树的停止点是当前的根节点的值 node.right = build(preorder, inorder, stop); // 右子树的停止点是当前树的停止点 return node; } }
21.从中序与后序遍历序列构造二叉树
题目链接：106. 从中序与后序遍历序列构造二叉树
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
示例 1:
输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]
示例 2:
输入：inorder = [-1], postorder = [-1]
输出：[-1]
提示:
1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder 和 postorder 都由 不同 的值组成
postorder 中每一个值都在 inorder 中
inorder 保证是树的中序遍历
postorder 保证是树的后序遍历
题解：
方法：递归 分治
/** * 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 { HashMap<Integer,Integer> memo = new HashMap<>(); int[] post; public TreeNode buildTree(int[] inorder, int[] postorder) { for(int i = 0;i < inorder.length; i++) memo.put(inorder[i], i); post = postorder; TreeNode root = buildTree(0, inorder.length - 1, 0, post.length - 1); return root; } public TreeNode buildTree(int is, int ie, int ps, int pe) { if(ie < is || pe < ps) return null; int root = post[pe]; int ri = memo.get(root); TreeNode node = new TreeNode(root); node.left = buildTree(is, ri - 1, ps, ps + ri - is - 1); node.right = buildTree(ri + 1, ie, ps + ri - is, pe - 1); return node; } }
22.根据前序和后序遍历构造二叉树
题目链接：889. 根据前序和后序遍历构造二叉树
给定两个整数数组，preorder 和 postorder ，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。
如果存在多个答案，您可以返回其中 任何 一个。
示例 1：
输入：preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
输出：[1,2,3,4,5,6,7]
示例 2:
输入: preorder = [1], postorder = [1]
输出: [1]
提示：
1 <= preorder.length <= 30
1 <= preorder[i] <= preorder.length
preorder 中所有值都 不同
postorder.length == preorder.length
1 <= postorder[i] <= postorder.length
postorder 中所有值都 不同
保证 preorder 和 postorder 是同一棵二叉树的前序遍历和后序遍历
题解：
方法：递归
前序遍历：按照「根-左子树-右子树」的顺序遍历二叉树。
后序遍历：按照「左子树-右子树-根」的顺序遍历二叉树。
/** * 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 constructFromPrePost(int[] preorder, int[] postorder) { int n = preorder.length; if (n == 0) { // 空节点 return null; } if (n == 1) { // 叶子节点 return new TreeNode(preorder[0]); } int leftSize = indexOf(postorder, preorder[1]) + 1; // 左子树的大小 int[] pre1 = Arrays.copyOfRange(preorder, 1, 1 + leftSize); int[] pre2 = Arrays.copyOfRange(preorder, 1 + leftSize, n); int[] post1 = Arrays.copyOfRange(postorder, 0, leftSize); int[] post2 = Arrays.copyOfRange(postorder, leftSize, n - 1); TreeNode left = constructFromPrePost(pre1, post1); TreeNode right = constructFromPrePost(pre2, post2); return new TreeNode(preorder[0], left, right); } // 返回 x 在 a 中的下标，保证 x 一定在 a 中 private int indexOf(int[] a, int x) { for (int i = 0; ; i++) { if (a[i] == x) { return i; } } } }
23. 二叉树中的第 K 大层和
题目链接：2583. 二叉树中的第 K 大层和
给你一棵二叉树的根节点 root 和一个正整数 k 。
树中的 层和 是指 同一层 上节点值的总和。
返回树中第 k 大的层和（不一定不同）。如果树少于 k 层，则返回 -1 。
注意，如果两个节点与根节点的距离相同，则认为它们在同一层。
示例 1：
输入：root = [5,8,9,2,1,3,7,4,6], k = 2
输出：13
解释：树中每一层的层和分别是：
- Level 1: 5
- Level 2: 8 + 9 = 17
- Level 3: 2 + 1 + 3 + 7 = 13
- Level 4: 4 + 6 = 10
第 2 大的层和等于 13 。
示例 2：
输入：root = [1,2,null,3], k = 1
输出：3
解释：最大的层和是 3 。
提示：
树中的节点数为 n
2 <= n <= 105
1 <= Node.val <= 106
1 <= k <= n
题解：
方法：BFS+排序
首先，利用 BFS，可以得到二叉树每一层的节点值之和。BFS 的同时，把每一层的节点值之和保存到一个列表 a 中，把 a 排序后就可以得到第 k 大。此外，也可以用快速选择得到第 k 大。
如果 k 大于 a 的长度，返回 −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 long kthLargestLevelSum(TreeNode root, int k) { List<Long> a = new ArrayList<>(); List<TreeNode> q = List.of(root); while (!q.isEmpty()) { long sum = 0; List<TreeNode> tmp = q; q = new ArrayList<>(); for (TreeNode node : tmp) { sum += node.val; if (node.left != null) q.add(node.left); if (node.right != null) q.add(node.right); } a.add(sum); } int n = a.size(); if (k > n) { return -1; } Collections.sort(a); return a.get(n - k); } }
24.二叉搜索树最近节点查询
题目链接：2476. 二叉搜索树最近节点查询
给你一个 二叉搜索树 的根节点 root ，和一个由正整数组成、长度为 n 的数组 queries 。
请你找出一个长度为 n 的 二维 答案数组 answer ，其中 answer[i] = [mini, maxi] ：
- mini 是树中小于等于 queries[i] 的 最大值 。如果不存在这样的值，则使用 -1 代替。
- maxi 是树中大于等于 queries[i] 的 最小值 。如果不存在这样的值，则使用 -1 代替。
返回数组 answer 。
示例 1 ：
输入：root = [6,2,13,1,4,9,15,null,null,null,null,null,null,14], queries
= [2,5,16]
输出：[[2,2],[4,6],[15,-1]]
解释：按下面的描述找出并返回查询的答案：
- 树中小于等于 2 的最大值是 2 ，且大于等于 2 的最小值也是 2 。所以第一个查询的答案是 [2,2] 。
- 树中小于等于 5 的最大值是 4 ，且大于等于 5 的最小值是 6 。所以第二个查询的答案是 [4,6] 。
- 树中小于等于 16 的最大值是 15 ，且大于等于 16 的最小值不存在。所以第三个查询的答案是 [15,-1] 。
示例 2 ：
输入：root = [4,null,9], queries = [3]
输出：[[-1,4]]
解释：树中不存在小于等于 3 的最大值，且大于等于 3 的最小值是 4 。所以查询的答案是 [-1,4] 。
提示：
树中节点的数目在范围 [2, 105] 内
1 <= Node.val <= 106
n == queries.length
1 <= n <= 105
1 <= queries[i] <= 106
题解：
方法：中序遍历+二分查找
题目没说二叉搜索树是平衡的，最坏情况下这棵树是一条链，此时单次询问的复杂度是 O(n) 的，其中 n 为二叉搜索树的节点个数。
设 j 是大于等于 q=queriesi的第一个数的下标，如果不存在则 j=n。
- 对于 maxi:
- 如果 j<n，那么 maxi=a[j]。
- 否则 maxi=−1。
- 对于 mini：
- 如果 j<n 且 a[j]=q，那么 mini=a[j]。
- 否则如果 j>0，那么 mini=a[j−1]。
- 否则 mini=−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<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) { List<Integer> arr = new ArrayList<>(); dfs(root, arr); int n = arr.size(); int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = arr.get(i); // 转成数组，效率更高 } List<List<Integer>> ans = new ArrayList<>(queries.size()); // 预分配空间 for (int q : queries) { int j = lowerBound(a, q); int mx = j == n ? -1 : a[j]; if (j == n || a[j] != q) { // a[j]>q, a[j-1]<q j--; } int mn = j < 0 ? -1 : a[j]; ans.add(List.of(mn, mx)); } return ans; } private void dfs(TreeNode node, List<Integer> a) { if (node == null) { return; } dfs(node.left, a); a.add(node.val); dfs(node.right, a); } // 见 https://www.bilibili.com/video/BV1AP41137w7/ private int lowerBound(int[] a, int target) { int left = -1, right = a.length; // 开区间 (left, right) while (left + 1 < right) { // 区间不为空 int mid = (left + right) >>> 1; // 比 /2 快 if (a[mid] >= target) { right = mid; // 范围缩小到 (left, mid) } else { left = mid; // 范围缩小到 (mid, right) } } return right; } }
25.二叉搜索树的最近公共祖先
题目链接：235. 二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。
题解：
方法：递归
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { int x = root.val; if (p.val < x && q.val < x) { // p 和 q 都在左子树 return lowestCommonAncestor(root.left, p, q); } if (p.val > x && q.val > x) { // p 和 q 都在右子树 return lowestCommonAncestor(root.right, p, q); } return root; // 其它 } }
下接：【题解】—— LeetCode一周小结9
