LeetCode 热题 100 之 230. 二叉搜索树中第 K 小的元素 199. 二叉树的右视图 114. 二叉树展开为链表

230. 二叉搜索树中第 K 小的元素199. 二叉树的右视图114. 二叉树展开为链表230. 二叉搜索树中第 K 小的元素/** * 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 count 0; private int res 0; public int kthSmallest(TreeNode root, int k) { inorder(root, k); return res; } private void inorder(TreeNode node, int k) { if (node null) return; inorder(node.left, k); // 访问当前节点计数1 count; if (count k) { res node.val; return; } inorder(node.right, k); } }解法思路1递归中序遍历思路递归执行中序遍历用计数器记录访问顺序当计数等于 K 时返回对应值。class Solution { public int kthSmallest(TreeNode root, int k) { StackTreeNode stack new Stack(); TreeNode cur root; while (!stack.isEmpty() || cur ! null) { // 遍历到最左节点 while (cur ! null) { stack.push(cur); cur cur.left; } // 弹出栈顶当前最小元素 cur stack.pop(); k--; if (k 0) return cur.val; // 找到第K小元素直接返回 // 处理右子树 cur cur.right; } return -1; // 题目保证k合法不会走到这里 } }解法思路2迭代中序遍历推荐可提前终止思路用栈模拟中序遍历访问到第 K 个元素时直接返回无需遍历整棵树效率更高。灵神写法一记录答案在中序遍历即「左-根-右」的过程中每次递归完左子树就把 k 减少 1表示我们按照中序遍历访问到了一个节点。如果减一后 k 变成 0那么答案就是当前节点的值用一个外部变量 ans 记录。class Solution { private int ans; private int k; public int kthSmallest(TreeNode root, int k) { this.k k; dfs(root); return ans; } private void dfs(TreeNode node) { if (node null || k 0) { return; } dfs(node.left); // 左 if (--k 0) { ans node.val; // 根 } dfs(node.right); // 右 } } 作者灵茶山艾府 链接https://leetcode.cn/problems/kth-smallest-element-in-a-bst/solutions/2952810/zhong-xu-bian-li-pythonjavaccgojsrust-by-wc02/ 来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。灵神写法二不记录答案 提前返回写法一使用了一个外部变量记录答案能否不使用外部变量记录呢可以做法如下递归边界如果当前节点是空节点返回 −1表示没有找到。注意题目保证节点值非负。执行中序遍历先递归左子树。判断左子树的返回值 leftRes 是否为 −1。如果不是 −1说明我们在左子树中找到了答案返回 leftRes。如果是 −1说明尚未找到答案继续下一步。把 k 减少 1。如果 k0那么答案就是当前节点值返回当前节点值。现在答案要么在当前节点的右子树中要么在除了当前子树的其余节点中。递归右子树如果答案在右子树中那么直接返回答案如果答案不在右子树中那么右子树也会返回 −1由于当前子树搜索完毕所以当前子树没有找到答案返回 −1。综上所述可以直接返回右子树的返回值。class Solution { private int k; public int kthSmallest(TreeNode root, int k) { this.k k; return dfs(root); } private int dfs(TreeNode node) { if (node null) { return -1; // 题目保证节点值非负用 -1 表示没有找到 } int leftRes dfs(node.left); if (leftRes ! -1) { // 答案在左子树中 return leftRes; } if (--k 0) { // 答案就是当前节点 return node.val; } return dfs(node.right); // 右子树会返回答案或者 -1 } } 作者灵茶山艾府 链接https://leetcode.cn/problems/kth-smallest-element-in-a-bst/solutions/2952810/zhong-xu-bian-li-pythonjavaccgojsrust-by-wc02/ 来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。199. 二叉树的右视图/** * 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 ListInteger rightSideView(TreeNode root) { ListInteger res new ArrayList(); if (root null) return res; QueueTreeNode queue new LinkedList(); queue.offer(root); while (!queue.isEmpty()) { int levelSize queue.size(); // 遍历当前层所有节点只取最后一个 for (int i 0; i levelSize; i) { TreeNode node queue.poll(); // 是当前层最后一个节点加入结果 if (i levelSize - 1) { res.add(node.val); } // 子节点入队 if (node.left ! null) queue.offer(node.left); if (node.right ! null) queue.offer(node.right); } } return res; } }class Solution { public ListInteger rightSideView(TreeNode root) { if (root null) { return List.of(); } ListInteger ans new ArrayList(); ListTreeNode cur List.of(root); while (!cur.isEmpty()) { ans.add(cur.getLast().val); ListTreeNode nxt new ArrayList(); for (TreeNode node : cur) { if (node.left ! null) nxt.add(node.left); if (node.right ! null) nxt.add(node.right); } cur nxt; } return ans; } } 作者灵茶山艾府 链接https://leetcode.cn/problems/binary-tree-right-side-view/solutions/2015061/ru-he-ling-huo-yun-yong-di-gui-lai-kan-s-r1nc/ 来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。解题思路1BFS思路按层遍历二叉树每一层只取最后一个节点最右侧节点即为右视图节点。class Solution { private ListInteger res new ArrayList(); public ListInteger rightSideView(TreeNode root) { dfs(root, 0); return res; } private void dfs(TreeNode node, int depth) { if (node null) return; // 首次访问该深度层级说明是最右侧节点 if (depth res.size()) { res.add(node.val); } // 先遍历右子树再遍历左子树 dfs(node.right, depth 1); dfs(node.left, depth 1); } }class Solution { public ListInteger rightSideView(TreeNode root) { if (root null) { return List.of(); } ListInteger ans new ArrayList(); ListTreeNode cur List.of(root); while (!cur.isEmpty()) { ans.add(cur.getLast().val); ListTreeNode nxt new ArrayList(); for (TreeNode node : cur) { if (node.left ! null) nxt.add(node.left); if (node.right ! null) nxt.add(node.right); } cur nxt; } return ans; } } 作者灵茶山艾府 链接https://leetcode.cn/problems/binary-tree-right-side-view/solutions/2015061/ru-he-ling-huo-yun-yong-di-gui-lai-kan-s-r1nc/ 来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。解题思路2DFS思路按照「根 → 右 → 左」的顺序遍历保证每一层第一个被访问的节点就是最右侧节点用深度记录层级首次访问该层级时加入结果。114. 二叉树展开为链表/** * 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 void flatten(TreeNode root) { ListTreeNode list new ArrayList(); preorder(root, list); // 依次修改指针 for (int i 1; i list.size(); i) { TreeNode prev list.get(i - 1); TreeNode curr list.get(i); prev.left null; prev.right curr; } } // 先序遍历收集节点 private void preorder(TreeNode root, ListTreeNode list) { if (root null) return; list.add(root); preorder(root.left, list); preorder(root.right, list); } }解法思路1递归法先序遍历 尾插思路按先序遍历顺序收集所有节点再依次修改指针将前一节点的right指向后一节点left置空。class Solution { public void flatten(TreeNode root) { if (root null) return; // 递归展开左右子树 flatten(root.left); flatten(root.right); // 保存原右子树 TreeNode right root.right; // 将左子树挂到根的右指针 root.right root.left; root.left null; // 找到当前右子树的末尾将原右子树挂到末尾 TreeNode p root; while (p.right ! null) { p p.right; } p.right right; } }解法思路2递归法先序遍历 尾插思路利用先序遍历的结构将左子树插入到根节点和右子树之间递归处理左右子树无需额外空间。class Solution { public void flatten(TreeNode root) { TreeNode curr root; while (curr ! null) { if (curr.left ! null) { // 找到左子树的最右节点先序遍历中 curr 的前驱 TreeNode pre curr.left; while (pre.right ! null) { pre pre.right; } // 将右子树挂到前驱的右指针 pre.right curr.right; // 将左子树挂到 curr 的右指针左指针置空 curr.right curr.left; curr.left null; } // 移动到下一个节点 curr curr.right; } } }解法思路3迭代法Morris 先序遍历O (1) 空间思路用 Morris 遍历实现先序遍历过程中直接修改指针原地展开无需递归栈和额外空间。class Solution { private TreeNode head; public void flatten(TreeNode root) { if (root null) { return; } flatten(root.right); flatten(root.left); root.left null; root.right head; // 头插法相当于链表的 root.next head head root; // 现在链表头节点是 root } } 作者灵茶山艾府 链接https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/solutions/2992172/liang-chong-fang-fa-tou-cha-fa-fen-zhi-p-h9bg/ 来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。解法思路4头插法采用头插法构建链表也就是从节点 6 开始在 6 的前面插入 5在 5 的前面插入 4依此类推。为此要按照 6→5→4→3→2→1 的顺序访问节点。如何遍历这棵树才能实现这个顺序按照右子树 - 左子树 - 根的顺序 DFS 这棵树。DFS 的同时记录当前链表的头节点为 head。一开始 head 是空节点。具体来说如果当前节点为空返回。递归右子树。递归左子树。把 root.left 置为空。头插法把 root 插在 head 的前面也就是 root.righthead。现在 root 是链表的头节点把 head 更新为 root。class Solution { public void flatten(TreeNode root) { dfs(root); } private TreeNode dfs(TreeNode root) { if (root null) { return null; } TreeNode leftTail dfs(root.left); TreeNode rightTail dfs(root.right); if (leftTail ! null) { leftTail.right root.right; // 左子树链表 - 右子树链表 root.right root.left; // 当前节点 - 左右子树合并后的链表 root.left null; } return rightTail ! null ? rightTail : leftTail ! null ? leftTail : root; } } 作者灵茶山艾府 链接https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/solutions/2992172/liang-chong-fang-fa-tou-cha-fa-fen-zhi-p-h9bg/ 来源力扣LeetCode 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。解法思路5分治考虑分治假如我们计算出了 root1 左子树的链表 2→3→4以及右子树的链表 5→6那么接下来只需要穿针引线把节点 1 和两条链表连起来先把 2→3→4 和 5→6 连起来也就是左子树链表尾节点 4 的 right 更新为节点 5即 root.right得到 2→3→4→5→6。然后把 1 和 2→3→4→5→6 连起来也就是节点 1 的 right 更新为节点 2即 root.left得到 1→2→3→4→5→6。最后把 root.left 置为空。上面的过程我们需要知道左子树链表的尾节点 4。所以 DFS 需要返回链表的尾节点。链表合并完成后返回合并后的链表的尾节点也就是右子树链表的尾节点。如果右子树是空的则返回左子树链表的尾节点。如果左右子树都是空的返回当前节点。总结这几道二叉树高频题核心思路清晰统一背熟模板即可举一反三二叉搜索树第 K 小利用 BST 性质中序遍历是升序递归 / 迭代找到第 K 个节点即为答案二叉树右视图BFS 取每层最后一个节点或 DFS 优先右遍历按深度记录首个节点二叉树展开为链表先序遍历重构、递归拼接左右子树、Morris 遍历省空间、反向头插、分治返回尾节点多种写法本质都是按先序修改指针左置空右相连。