二叉树相关
#LeetCode#算法#二叉树 2023-12-31

二叉树相关算法题

前言

不讲概念性的东西，结合力扣上的题目，练习二叉树相关知识。

遍历方式

前序遍历

二叉树的前序遍历顺序：根节点 -> 左子树 -> 右子树

题目： 144. 二叉树的前序遍历 - 力扣（LeetCode）

递归实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func preorderTraversal(root *TreeNode) []int {
    var f func(root *TreeNode) []int
    var res []int
    f = func(root *TreeNode) []int {
        // 当前节点为 nil，返回
        if root == nil{
            return res
        }

        // 先将当前节点加入答案数组
        res = append(res, root.Val)
        // 遍历左子树
        if root.Left != nil{
            f(root.Left)
        }
        // 遍历右子树
        if root.Right != nil{
            f(root.Right)
        }
        return res
    }
    f(root)
    return res
}

迭代实现：这个实现可以用一个栈结构去实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func preorderTraversal(root *TreeNode) []int {
    if root == nil{
        return nil
    }

    var res []int
    var stack []*TreeNode
    var node = root

    for node != nil || len(stack) > 0{
        for node != nil{
            res = append(res, node.Val)
            stack = append(stack, node)
            node = node.Left
        }
        node = stack[len(stack) - 1].Right
        stack = stack[:len(stack) - 1]
    }
    
    return res
}

中序遍历

二叉树的中序遍历：左子树 -> 根节点 -> 右子树

题目：94. 二叉树的中序遍历 - 力扣（LeetCode）

递归实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func inorderTraversal(root *TreeNode) []int {
    var f func(*TreeNode) []int
    var res []int
    f = func(root *TreeNode) []int{
        if root == nil{
            return res
        }
        f(root.Left)
        res = append(res, root.Val)
        f(root.Right)
        return res
    }
    f(root)
    return res
}

迭代实现：与前序遍历类似，可以用一个栈结构实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func inorderTraversal(root *TreeNode) []int {
    var stack []*TreeNode
    var res []int
    var node = root

    for node != nil || len(stack) > 0{
        for node != nil{
            stack = append(stack, node)
            node = node.Left
        }
        res = append(res, stack[len(stack) - 1].Val)
        if stack[len(stack) - 1].Right != nil{
            node = stack[len(stack) - 1].Right
        }
        stack = stack[:len(stack) - 1]
    }
    return res
}

后序遍历

二叉树的后序遍历：左子树 -> 右子树 -> 根节点

题目：145. 二叉树的后序遍历 - 力扣（LeetCode）

递归实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func postorderTraversal(root *TreeNode) []int {
    var f func(*TreeNode) []int
    var res []int
    f = func(root *TreeNode) []int{
        if root == nil{
            return res
        }

        f(root.Left)
        f(root.Right)
        res = append(res, root.Val)
        return res
    }
    f(root)
    return res
}

层序遍历

层序遍历是一层一层从左到右遍历二叉树。我们可以运用广度优先搜索的知识去遍历这颗二叉树。

题目：

递归实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func levelOrder(root *TreeNode) [][]int {
    if root == nil{
        return nil
    }
    var res = make([][]int, 1)
    var f func(*TreeNode, int)
    
    f = func(root *TreeNode, level int){
        if root == nil{
            return
        }
        res[level] = append(res[level], root.Val)
        if root.Left != nil || root.Right != nil{
            if level+1 >= len(res){
                res = append(res, []int{})
            }
            f(root.Left, level+1)
            f(root.Right, level+1)
        }
    }
    f(root, 0)
    return res
}

迭代实现：像大多数实现一样，使用队列去实现广度优先搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func levelOrder(root *TreeNode) [][]int {
    if root == nil{
        return nil
    }

    var res = make([][]int, 0)
    var queue = []*TreeNode{root}

    for i := 0; len(queue) > 0; i++{
        res = append(res, []int{})
        qLen := len(queue)
        for j := 0; j < qLen; j++{
            now := queue[0]
            queue = queue[1:]
            res[i] = append(res[i], now.Val)

            if now.Left != nil{
                queue = append(queue, now.Left)
            }
            if now.Right != nil{
                queue = append(queue, now.Right)
            }
        }
    }
    return res
}

层序遍历的拓展

题目：103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
func zigzagLevelOrder(root *TreeNode) [][]int {
    if root == nil{
        return nil
    }
    var q = []*TreeNode{root}
    var res [][]int

    for i := 0; len(q) > 0; i++{
        res = append(res, []int{})
        qLen := len(q)

        // 遍历当前队列
        for j := 0; j < qLen; j++{
            now := q[0]
            res[i] = append(res[i], now.Val)
            q = q[1:]

            if now.Left != nil{
                q = append(q, now.Left)
            }
            if now.Right != nil{
                q = append(q, now.Right)
            }
        }

        if i % 2 == 1{
            // 反着遍历，交换数组元素
            n := len(res[i])
            for j := 0; j < len(res[i]) / 2; j++{
                res[i][j], res[i][n - j - 1] = res[i][n - j - 1], res[i][j]
            }
        }
    }
          
    return res
}

题目：513. 找树左下角的值 - 力扣（LeetCode）

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func findBottomLeftValue(root *TreeNode) int {
    // 答案，以及现在遍历的最大一层
    var ans, maxLevel int
    var dfs func(*TreeNode, int)
    dfs = func(node *TreeNode, level int){
        if node == nil{
            return
        }

        if level > maxLevel{
            // 这一层第一个遍历到的就是最左边的元素
            ans = node.Val
        }
        maxLevel = max(level, maxLevel)

        dfs(node.Left, level+1)
        dfs(node.Right, level+1)
    }
    dfs(root, 1)
    return ans
}

func max(x, y int) int{
    if x > y {
        return x
    }
    return y
}

我也不知道怎么分类了

104. 二叉树的最大深度

思路

递归遍历这棵二叉树。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func maxDepth(root *TreeNode) int {
    var res int
    var f func(*TreeNode, int)
    f = func(root *TreeNode, depth int){
        if root == nil{
            return
        }
        res = max(res, depth)
        f(root.Left, depth + 1)
        f(root.Right, depth + 1)
    }
    f(root, 1)
    return res
}

func max(x, y int) int{
    if x > y{
        return x
    }
    return y
}

100. 相同的树

思路

递归比较两棵树每个节点的值，遇到结构不一致时，返回 false。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func isSameTree(p *TreeNode, q *TreeNode) bool {
    var res = true
    var f func(p *TreeNode, q *TreeNode) 
    f = func(p *TreeNode, q *TreeNode) {
        if p == nil && q == nil{
            return
        }
        if p == nil || q == nil{
            res = false
            return
        }
        if p.Val != q.Val{
            res = false
            return
        }
        f(p.Left, q.Left)
        f(p.Right, q.Right)
    }

    f(p, q)
    return res
}

101. 对称二叉树

思路

上一题相反的比较即可

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func isSymmetric(root *TreeNode) bool {
    var res = true
    var f func(p *TreeNode, q *TreeNode) 
    f = func(p *TreeNode, q *TreeNode) {
        if p == nil && q == nil{
            return
        }
        if p == nil || q == nil{
            res = false
            return
        }
        if p.Val != q.Val{
            res = false
            return
        }
        f(p.Left, q.Right)
        f(p.Right, q.Left)
    }

    f(root.Left, root.Right)
    return res
}

110. 平衡二叉树

思路

自顶向下递归，逐个验证每个节点是否为平衡的二叉树（也就是左右子树高度相差是否大于 1）

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func isBalanced(root *TreeNode) bool {
    if root == nil{
        return true
    }
    return abs(height(root.Left) - height(root.Right)) <= 1 && isBalanced(root.Left) && isBalanced(root.Right)
}

func height(root *TreeNode) int{
    if root == nil{
        return 0
    }
    return max(height(root.Left), height(root.Right)) + 1
}

func max(x, y int) int{
    if x > y {
        return x
    }
    return y
}

func abs(x int) int{
    if x < 0{
        return -x
    }
    return x
}

199. 二叉树的右视图

思路

我的想法是层序遍历一遍二叉树，每一层最右边（也就是子数组的最后一个元素），就是右视图能看到的。这是广度优先搜索的解法。

关于深度优先搜索，我觉得官解的一句话可以让人勃然大怒（哦恍然大悟）。

我们对树进行深度优先搜索，在搜索过程中，我们总是先访问右子树。那么对于每一层来说，我们在这层见到的第一个结点一定是最右边的结点。

代码实现

广度优先搜索（层序遍历）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func rightSideView(root *TreeNode) []int {
    if root == nil{
        return nil
    }

    var res [][]int
    var ans []int
    var q = []*TreeNode{root}

    for i := 0; len(q) > 0; i++{
        res = append(res, []int{})
        qLen := len(q)

        for j := 0; j < qLen; j++{
            now := q[0]
            q = q[1:]
            res[i] = append(res[i], now.Val)

            if now.Left != nil{
                q = append(q, now.Left)
            }
            if now.Right != nil{
                q = append(q, now.Right)
            }
        }
        ans = append(ans, res[i][len(res[i]) - 1])
    }
    
    return ans
}

深度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func rightSideView(root *TreeNode) []int {
    if root == nil{
        return nil
    }

    var ans = []int{root.Val}
    var f func(*TreeNode, int)
    f = func(root *TreeNode, level int){
        if root == nil{
            return 
        }

        if len(ans) < level{
            // 这一层碰到的第一个节点
            ans = append(ans, root.Val)
        }
        f(root.Right, level + 1)
        f(root.Left, level + 1)
    }
    f(root, 1)
    return ans
}

1026. 节点与其祖先之间的最大差值

思路：

使用自顶向下的递归，每次递归传递当前的最大值和最小值，并更新。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func maxAncestorDiff(root *TreeNode) int {
    var dfs func(*TreeNode, int, int)
    var res int
    dfs = func(root *TreeNode, maxInt, minInt int){
        if root == nil{
            return 
        }

        maxInt = max(maxInt, root.Val)
        minInt = min(minInt, root.Val)
        res = max(res, maxInt - minInt)
        dfs(root.Left, maxInt, minInt)
        dfs(root.Right, maxInt, minInt)
    }
    dfs(root, root.Val, root.Val)
    return res
}

func max(x, y int) int{if x > y{return x}; return y}
func min(x, y int) int{if x > y{return y}; return x}

1080. 根到叶子路径上的不足节点

思路

因为需要遍历到叶子节点。我们可以递归的遍历到叶子节点，每遍历一个节点 limit 就减去当前节点的值。如果本次遍历 limit 的值大于 0，那么需要删除。如果小于等于零，这个叶子节点不需要删除，那么我们返回空。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func sufficientSubset(root *TreeNode, limit int) *TreeNode {
    if root == nil{
        return nil
    }
    limit -= root.Val

    if root.Left == nil && root.Right == nil{
        // 当前节点是叶子节点
        if limit > 0{
            return nil
        }
        return root
    }

    root.Left = sufficientSubset(root.Left, limit)
    root.Right = sufficientSubset(root.Right, limit)

    if root.Left == nil && root.Right == nil{
        // 孩子都被删掉了
        return nil
    }

    return root
}

1110. 删点成林

思路

我的想法是，使用递归，深度优先搜索这颗二叉树，传递一个参数 isParent，当为 true 且不被删除时，加入答案。在开始时，会检查是否需要被删除，如果被删除，这个节点设为 nil。我们需要再次调用 dfs 这个函数，去遍历被删除节点的左右子树。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
func delNodes(root *TreeNode, to_delete []int) []*TreeNode {
    var element = make(map[int]struct{})
    for i := range to_delete{
        element[to_delete[i]] = struct{}{}
    }

    var dfs func(*TreeNode, bool) *TreeNode
    var ans []*TreeNode
    dfs = func(node *TreeNode, isParent bool) *TreeNode {
        if node == nil{
            return nil
        }

        if _, ok := element[node.Val]; ok{
            // 需要删除
            dfs(node.Left, true)
            dfs(node.Right, true)

            return nil
        }

        // 否则，继续往下
        node.Left = dfs(node.Left, false)
        node.Right = dfs(node.Right, false)

        if isParent{
            ans = append(ans, node)
        }
        return node
    }
    dfs(root, true)
    return ans
}

98. 验证二叉搜索树

思路：

关键：当验证左子树时，left 是左子树节点，而 right 是它的父节点。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func isValidBST(root *TreeNode) bool {
    var f func(*TreeNode, int, int) bool
    f = func(node *TreeNode, left, right int) bool {
        if node == nil{
            return true
        }
        x := node.Val
        return x > left &&
                x < right &&
                f(node.Left, left, x) &&
                f(node.Right, x, right)
    }

    return f(root, math.MinInt, math.MaxInt)
}

236. 二叉树的最近公共祖先

思路：

查找每个节点的左右子树是否包含 p，q，当这个节点返回的左右节点都不为空（证明它是 p，q 的父节点）。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if root == nil || root == p || root == q{
        return root
    }
    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)

    if left != nil && right != nil{
        return root
    }
    if left != nil{
        return left
    }
    return right
}

235. 二叉搜索树的最近公共祖先

思路

本题可以用上题代码。但是可以利用上二叉搜索树这个特点。

代码实现

1
2
3
4
5
6
7
8
9
10
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	x := root.Val
    if x > p.Val && x > q.Val{
        return lowestCommonAncestor(root.Left, p, q)
    }
    if x < p.Val && x < q.Val{
        return lowestCommonAncestor(root.Right, p, q)
    }
    return root
}

1123. 最深叶节点的最近公共祖先

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
func lcaDeepestLeaves(root *TreeNode) *TreeNode {
    // 左右子树深度相同，那么这个就是它们的公共祖先
    var maxLevel int
    var f func(*TreeNode, int) int
    var ans *TreeNode
    f = func(node *TreeNode, level int) int{
        if node == nil{
            maxLevel = max(maxLevel, level)
            return level
        }

        left := f(node.Left, level+1)
        right := f(node.Right, level+1)

        if left == right && left == maxLevel{
            ans = node
        }
        return max(left, right)
    }
    f(root, 0)
    return ans
}

func max(x, y int) int{
    if x > y{
      return x
    }
    return y
}