236. 二叉树的最近公共祖先 Lowest Common Ancestor of a Binary-tree
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。
因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1
提示：
- 树中节点数目在范围
[2, 10^5]内。 -10^9 <= Node.val <= 10^9- 所有
Node.val互不相同。 p != qp和q均存在于给定的二叉树中。
代码1：迭代法
- 使用栈将后序遍历改为迭代遍历，同时记录每个节点的父节点；
- 找到 p 和 q 的所有祖先节点，并存储在一个 hash set 中；
- 从 p 开始，不断向上查找，记录其祖先节点并存在另一个 hash set 中；
- 从 q 开始向上查找祖先节点，如果已经在上一个 hash set 中存在，则找到了最近公共祖先节点。
package main import ( "fmt" "strings" ) const null = -1 << 31 type TreeNode struct { Val int Left *TreeNode Right *TreeNode } func buildTree(nums []int) *TreeNode { if len(nums) == 0 { return nil } root := &TreeNode{Val: nums[0]} Queue := []*TreeNode{root} idx := 1 for idx < len(nums) { node := Queue[0] Queue = Queue[1:] if nums[idx] != null { node.Left = &TreeNode{Val: nums[idx]} Queue = append(Queue, node.Left) } idx++ if idx < len(nums) && nums[idx] != null { node.Right = &TreeNode{Val: nums[idx]} Queue = append(Queue, node.Right) } idx++ } return root } func levelOrder(root *TreeNode) [][]int { res := [][]int{} if root == nil { return res } Queue := []*TreeNode{root} for len(Queue) > 0 { level := []int{} n := len(Queue) for i := 0; i < n; i++ { cur := Queue[0] Queue = Queue[1:] level = append(level, cur.Val) if cur.Left != nil { Queue = append(Queue, cur.Left) } if cur.Right != nil { Queue = append(Queue, cur.Right) } } res = append(res, level) } return res } func Array2DToString(array [][]int) string { if len(array) == 0 { return "[]" } arr2str := func(arr []int) string { res := "[" for i := 0; i < len(arr); i++ { res += fmt.Sprint(arr[i]) if i != len(arr)-1 { res += "," } } return res + "]" } res := make([]string, len(array)) for i, arr := range array { res[i] = arr2str(arr) } return strings.Join(strings.Fields(fmt.Sprint(res)), ",") } func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode { parent := make(map[*TreeNode]*TreeNode) stack := []*TreeNode{root} for len(stack) > 0 { node := stack[len(stack)-1] stack = stack[:len(stack)-1] if node.Left != nil { parent[node.Left] = node stack = append(stack, node.Left) } if node.Right != nil { parent[node.Right] = node stack = append(stack, node.Right) } } ancestors := make(map[*TreeNode]bool) for p != nil { ancestors[p] = true p = parent[p] } for q != nil { if ancestors[q] { return q } q = parent[q] } return nil } func main() { nums := []int{3, 5, 1, 6, 2, 0, 8, null, null, 7, 4} root := buildTree(nums) p, q := root.Left, root.Right fmt.Println(Array2DToString(levelOrder(root))) fmt.Println(lowestCommonAncestor(root, p, q).Val) q = root.Left.Right.Right fmt.Println(lowestCommonAncestor(root, p, q).Val) nums = []int{1, 2} root = buildTree(nums) p, q = root, root.Left fmt.Println(Array2DToString(levelOrder(root))) fmt.Println(lowestCommonAncestor(root, p, q).Val) }
代码2： 递归法
- 如果当前节点为 nil 或者等于 p 或 q 中的任意一个，则返回当前节点；
- 在左子树中查找是否包含 p 或 q，返回值为 l；
- 在右子树中查找是否包含 p 或 q，返回值为 r；
- a) 如果 l 和 r 都不为空，说明 p 和 q 分别在当前节点的左右子树，则当前节点就是它们的最近公共祖先节点；
b) 如果 l 为空，说明 p 和 q 都在右子树中，则最近公共祖先节点一定在右子树中，返回 r；
c) 如果 r 为空，说明 p 和 q 都在左子树中，则最近公共祖先节点一定在左子树中，返回 l。
package main import ( "fmt" "strings" ) const null = -1 << 31 type TreeNode struct { Val int Left *TreeNode Right *TreeNode } func buildTree(nums []int) *TreeNode { if len(nums) == 0 { return nil } root := &TreeNode{Val: nums[0]} Queue := []*TreeNode{root} idx := 1 for idx < len(nums) { node := Queue[0] Queue = Queue[1:] if nums[idx] != null { node.Left = &TreeNode{Val: nums[idx]} Queue = append(Queue, node.Left) } idx++ if idx < len(nums) && nums[idx] != null { node.Right = &TreeNode{Val: nums[idx]} Queue = append(Queue, node.Right) } idx++ } return root } func levelOrder(root *TreeNode) [][]int { res := [][]int{} if root == nil { return res } Queue := []*TreeNode{root} for len(Queue) > 0 { level := []int{} n := len(Queue) for i := 0; i < n; i++ { cur := Queue[0] Queue = Queue[1:] level = append(level, cur.Val) if cur.Left != nil { Queue = append(Queue, cur.Left) } if cur.Right != nil { Queue = append(Queue, cur.Right) } } res = append(res, level) } return res } func Array2DToString(array [][]int) string { if len(array) == 0 { return "[]" } arr2str := func(arr []int) string { res := "[" for i := 0; i < len(arr); i++ { res += fmt.Sprint(arr[i]) if i != len(arr)-1 { res += "," } } return res + "]" } res := make([]string, len(array)) for i, arr := range array { res[i] = arr2str(arr) } return strings.Join(strings.Fields(fmt.Sprint(res)), ",") } func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode { if root == nil || root.Val == p.Val || root.Val == q.Val { return root } l := lowestCommonAncestor(root.Left, p, q) r := lowestCommonAncestor(root.Right, p, q) if l != nil && r != nil { // postorder return root } else if l == nil { return r } else { return l } } func main() { nums := []int{3, 5, 1, 6, 2, 0, 8, null, null, 7, 4} root := buildTree(nums) p, q := root.Left, root.Right fmt.Println(Array2DToString(levelOrder(root))) fmt.Println(lowestCommonAncestor(root, p, q).Val) q = root.Left.Right.Right fmt.Println(lowestCommonAncestor(root, p, q).Val) nums = []int{1, 2} root = buildTree(nums) p, q = root, root.Left fmt.Println(Array2DToString(levelOrder(root))) fmt.Println(lowestCommonAncestor(root, p, q).Val) }
输出：
[[3],[5,1],[6,2,0,8],[7,4]]
3
5
[[1],[2]]
1
865. 具有所有最深节点的最小子树 Smallest-subtree-with-all-the-deepest-nodes
给定一个根为 root 的二叉树，每个节点的深度是 该节点到根的最短距离 。
返回包含原始树中所有 最深节点 的 最小子树 。
如果一个节点在 整个树 的任意节点之间具有最大的深度，则该节点是 最深的 。
一个节点的 子树 是该节点加上它的所有后代的集合。
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4]
输出：[2,7,4]
解释：
我们返回值为 2 的节点，在图中用黄色标记。
在图中用蓝色标记的是树的最深的节点。
注意，节点 5、3 和 2 包含树中最深的节点，但节点 2 的子树最小，因此我们返回它。
示例 2：
输入：root = [1]
输出：[1]
解释：根节点是树中最深的节点。
示例 3：
输入：root = [0,1,3,null,2]
输出：[2]
解释：树中最深的节点为 2 ，有效子树为节点 2、1 和 0 的子树，但节点 2 的子树最小。
提示：
- 树中节点的数量在
[1, 500]范围内。 0 <= Node.val <= 500- 每个节点的值都是 独一无二 的。
注意：本题与力扣 1123 重复
代码：迭代法
- 使用栈将前序遍历改为迭代遍历，同时记录每个节点的深度；
- 找到树中所有最深节点的深度；
- 从根节点开始，不断向下查找，遇到最深深度的节点就返回。
package main import ( "fmt" "strings" ) const null = -1 << 31 type TreeNode struct { Val int Left *TreeNode Right *TreeNode } func buildTree(nums []int) *TreeNode { if len(nums) == 0 { return nil } root := &TreeNode{Val: nums[0]} Queue := []*TreeNode{root} idx := 1 for idx < len(nums) { node := Queue[0] Queue = Queue[1:] if nums[idx] != null { node.Left = &TreeNode{Val: nums[idx]} Queue = append(Queue, node.Left) } idx++ if idx < len(nums) && nums[idx] != null { node.Right = &TreeNode{Val: nums[idx]} Queue = append(Queue, node.Right) } idx++ } return root } func levelOrder(root *TreeNode) [][]int { res := [][]int{} if root == nil { return res } Queue := []*TreeNode{root} for len(Queue) > 0 { level := []int{} n := len(Queue) for i := 0; i < n; i++ { cur := Queue[0] Queue = Queue[1:] level = append(level, cur.Val) if cur.Left != nil { Queue = append(Queue, cur.Left) } if cur.Right != nil { Queue = append(Queue, cur.Right) } } res = append(res, level) } return res } func Array2DToString(array [][]int) string { if len(array) == 0 { return "[]" } arr2str := func(arr []int) string { res := "[" for i := 0; i < len(arr); i++ { res += fmt.Sprint(arr[i]) if i != len(arr)-1 { res += "," } } return res + "]" } res := make([]string, len(array)) for i, arr := range array { res[i] = arr2str(arr) } return strings.Join(strings.Fields(fmt.Sprint(res)), ",") } func subtreeWithAllDeepest(root *TreeNode) *TreeNode { depth := make(map[*TreeNode]int) stack := []*TreeNode{root} maxDepth := -1 if root.Left == nil && root.Right == nil { return root } for len(stack) > 0 { node := stack[len(stack)-1] stack = stack[:len(stack)-1] if node.Left != nil { depth[node.Left] = depth[node] + 1 stack = append(stack, node.Left) } if node.Right != nil { depth[node.Right] = depth[node] + 1 stack = append(stack, node.Right) } } for _, d := range depth { if d > maxDepth { maxDepth = d } } return dfs(root, depth, maxDepth) } func dfs(node *TreeNode, depth map[*TreeNode]int, maxDepth int) *TreeNode { if node == nil { return nil } if depth[node] == maxDepth { return node } left := dfs(node.Left, depth, maxDepth) right := dfs(node.Right, depth, maxDepth) if left != nil && right != nil { return node } else if left == nil { return right } else { return left } } func main() { nums := []int{3, 5, 1, 6, 2, 0, 8, null, null, 7, 4} root := buildTree(nums) fmt.Println(Array2DToString(levelOrder(root))) res := subtreeWithAllDeepest(root) fmt.Println(Array2DToString(levelOrder(res))) nums = []int{1} root = buildTree(nums) fmt.Println(Array2DToString(levelOrder(root))) res = subtreeWithAllDeepest(root) fmt.Println(Array2DToString(levelOrder(res))) nums = []int{0, 1, 3, null, 2} root = buildTree(nums) fmt.Println(Array2DToString(levelOrder(root))) res = subtreeWithAllDeepest(root) fmt.Println(Array2DToString(levelOrder(res))) }
输出：
[[3],[5,1],[6,2,0,8],[7,4]]
[[2],[7,4]]
[[1]]
[[1]]
[[0],[1,3],[2]]
[[2]]
1123. 最深叶节点的最近公共祖先 Lowest-common-ancestor-of-deepest-leaves
给你一个有根节点 root 的二叉树，返回它 最深的叶节点的最近公共祖先 。
回想一下：
- 叶节点 是二叉树中没有子节点的节点
- 树的根节点的 深度 为
0，如果某一节点的深度为d，那它的子节点的深度就是d+1 - 如果我们假定
A是一组节点S的 最近公共祖先，S中的每个节点都在以A为根节点的子树中，且A的深度达到此条件下可能的最大值。
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4]
输出：[2,7,4]
解释：我们返回值为 2 的节点，在图中用黄色标记。
在图中用蓝色标记的是树的最深的节点。
注意，节点 6、0 和 8 也是叶节点，但是它们的深度是 2 ，而节点 7 和 4 的深度是 3 。
示例 2：
输入：root = [1]
输出：[1]
解释：根节点是树中最深的节点，它是它本身的最近公共祖先。
示例 3：
输入：root = [0,1,3,null,2]
输出：[2]
解释：树中最深的叶节点是 2 ，最近公共祖先是它自己。
提示：
- 树中的节点数将在
[1, 1000]的范围内。 0 <= Node.val <= 1000- 每个节点的值都是 独一无二 的。
注意：本题与力扣 865 重复
🌟 每日一练刷题专栏 🌟
✨持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/
|
Rust每日一练 专栏 （2023.5.16~）更新中... |
|
Golang每日一练 专栏 （2023.3.11~）更新中... |
|
Python每日一练 专栏 （2023.2.18~2023.5.18）暂停更 |
|
C/C++每日一练 专栏 （2023.2.18~2023.5.18）暂停更 |
|
Java每日一练 专栏 （2023.3.11~2023.5.18）暂停更 |
