865. 具有所有最深节点的最小子树 Smallest

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^9Node.val互不相同p != qpq

代码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]]

[[1],[2]]

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]]

[[0],[1,3],[2]]

[[2]]

1123. 最深叶节点的最近公共祖先 Lowest-common-ancestor-of-deepest-leaves

root

回想一下：

0dd+1ASSAA

示例 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 重复

✨ 持续，努力奋斗做强刷题搬运工！

👍 点赞，你的认可是我坚持的动力！

🌟 收藏，你的青睐是我努力的方向！

✎ 评论，你的意见是我进步的财富！

	（2023.5.16~）更新中...
	（2023.3.11~）更新中...
	（2023.2.18~2023.5.18）暂停更
	（2023.2.18~2023.5.18）暂停更
	（2023.3.11~2023.5.18）暂停更