平衡二叉树 & 对称二叉树 & 二叉树中的最大路径和 & 二叉树的直径 & 另一棵树的子树 & 子结构判断 & 监控二叉树 & 路径总和 & 完全二叉树的节点个数 & 找树左下角的值——DFS

Author： SnowKagura
发布时间：July 9, 2025
9 views
No comments
1271 words
Categories： Leetcode

# 平衡二叉树

这个需要左右子树的深度差小于等于1，dfs解决

```go
func isBalanced(root *TreeNode) bool {
    _, balanced := valid(root)
    return balanced
}

func valid(root *TreeNode) (int, bool) {
    if root == nil {
        return 0, true
    }
    lh, lb := valid(root.Left)
    rh, rb := valid(root.Right)
    if !lb || !rb {
        return 0, false
    }
    if abs(lh - rh) > 1 {
        return 0, false
    }
    return max(lh, rh) + 1, true
}

func abs(val int) int {
    if val > 0 {
        return val
    }
    return -val
}
```

# 对称二叉树

这个需要左右子树的值相等且左子树的左节点等于右子树的右节点，且左子树的右节点等于右子树的左节点

```go
func isSymmetric(root *TreeNode) bool {
    if root == nil {
        return true
    }
    return dfs(root.Left, root.Right)
}

func dfs(left *TreeNode, right*TreeNode) bool {
    if left == nil && right == nil {
        return true
    }
    if left == nil && right != nil {
        return false
    }
    if left != nil && right == nil {
        return false
    }
    if left.Val != right.Val {
        return false
    }
    return dfs(left.Right, right.Left) && dfs(left.Left, right.Right)
}
```

# 二叉树中的最大路径和

这个需要后序遍历+左右子树和本身节点和的最大值，返回给上层的是单条分支的值，因为不能走回头路

```go
func maxPathSum(root *TreeNode) int {
    res := -1 << 31
    dfs(root, &res)
    return res
}

func dfs(root *TreeNode, maxVal *int) int {
    if root == nil {
        return 0
    }
    l := max(dfs(root.Left, maxVal), 0)
    r := max(dfs(root.Right, maxVal), 0)
    *maxVal = max(*maxVal, l + r + root.Val)
    return root.Val + max(l, r)
}
```

# 二叉树的直径

类似于二叉树中的最大路径和，只是这里不是节点上的值，而是路径长度

```go
func diameterOfBinaryTree(root *TreeNode) int {
    res := 0
    dfs(root, &res)
    return res
}

func dfs(root *TreeNode, maxVal *int) int {
    if root == nil {
        return 0
    }
    left := dfs(root.Left, maxVal)
    right := dfs(root.Right, maxVal)
    *maxVal = max(*maxVal, left + right)
    return 1 + max(left, right)
}
```

# 另一棵树的子树

这个问题其实有点类似于对称二叉树，都是找子树的值，只不过对称的条件和子树相等的条件有点不一样，需要当前节点，左节点，右节点都相等。

```go
func isSubtree(root *TreeNode, subRoot *TreeNode) bool {
    if root == nil {
        return subRoot == nil
    }
    left := isSubtree(root.Left, subRoot)
    right := isSubtree(root.Right, subRoot)
    return isIdentical(root, subRoot) || left || right
}

func isIdentical(a, b *TreeNode) bool {
    if a == nil && b == nil {
        return true
    }
    if a == nil || b == nil {
        return false
    }
    if a.Val != b.Val {
        return false
    }
    return isIdentical(a.Left, b.Left) && isIdentical(a.Right, b.Right)
}
```

# 子结构判断

这道题类似于另一棵树的子树，只是条件有所扩展，不是判断完全相等，而是需要有这个结构就可以，所以 B 为 nil 的情况实际上是 false 的，并且在 match 的时候 b 先走完就说明匹配上了，其他的逻辑都相同

```go
func isSubStructure(A *TreeNode, B *TreeNode) bool {
    // A 和 B 任意一个为 nil 都不可能满足子结构条件
    if A == nil || B == nil {
        return false
    }
    left := isSubStructure(A.Left, B)
    right := isSubStructure(A.Right, B)
    return match(A, B) || left || right
}

func match(a *TreeNode, b *TreeNode) bool {
    // b 先走完，说明匹配上了
    if b == nil {
        return true
    }
    // a 先走完，说明没匹配上
    if a == nil {
        return false
    }
    if a.Val != b.Val {
        return false
    }
    return match(a.Left, b.Left) && match(a.Right, b.Right)
}
```

# 监控二叉树

这道题是贪心，尽量把监控装在叶子结点的父节点，可以覆盖最多的节点数量，遵循这一条原则即可，我们可以归类出三个状态：被覆盖，未覆盖，装监控。

那么

- 如果当前节点的左右节点有装监控的，当前节点的状态肯定是被覆盖。
- 如果当前节点的左右节点有未覆盖的，当前节点肯定要装监控，答案累积加1。
- 如果当前节点的左右节点都是覆盖的，那么当前节点就是未覆盖状态，将问题向上抛。
- 如果当前节点为空，视作已覆盖，就可以满足在叶子结点的父节点装监控。

有了上述规则，我们就能得到最优的解

```go
const (
    NOT_COVERED int = iota
    COVERED
    HAS_CAMERA
)

func minCameraCover(root *TreeNode) int {
    res := 0
    var dfs func(root *TreeNode) int
    dfs = func(root *TreeNode) int {
        if root == nil {
            return COVERED
        }
        left := dfs(root.Left)
        right := dfs(root.Right)
        if left == NOT_COVERED || right == NOT_COVERED {
            res++
            return HAS_CAMERA
        }
        if left == HAS_CAMERA || right == HAS_CAMERA {
            return COVERED
        }
        return NOT_COVERED
    }
    if dfs(root) == NOT_COVERED {
        res++
    }
    return res
}
```

# 路径总和

这道题自己想出来了，就是遍历根节点到叶子节点的总和是否等于target。

```go
func hasPathSum(root *TreeNode, targetSum int) bool {
    if root == nil {
        return false
    }
    if root.Left == nil && root.Right == nil && root.Val == targetSum {
        return true
    }
    cur := targetSum - root.Val
    return hasPathSum(root.Left, cur) || hasPathSum(root.Right, cur)
}
```

# 完全二叉树的节点个数

这道题最简单的做法是全部遍历一遍，也就是所谓的后序遍历。

然后还有一种做法是利用完全二叉树的性质。

因为完全二叉树只有最底层可能不满，所以我们分别从左子树和右子树开始出发往下。

一直走左孩子走到叶子节点的这个高度，如果 lh = rh，说明左子树是满二叉树，可以直接用公式 $ 2^{lh} - 1 $ 获得左子树的节点个数，再加上根节点，就刚好是 $ 2^{lh} $ 个，然后再在右子树进行递归。

反之，说明右子树是满二叉树，整个过程就颠倒过来，这样做的时间复杂度只有 $(log_2n)^2$

```go
func countNodes(root *TreeNode) int {
    if root == nil {
        return 0
    }
    lh, rh := 0, 0
    for p := root.Left; p != nil; p = p.Left {
        lh++
    }
    for p := root.Right; p != nil; p = p.Left {
        rh++
    }
    if lh == rh {
        return (1 << lh) + countNodes(root.Right)
    }
    return (1 << rh) + countNodes(root.Left)
}
```

# 找树左下角的值

这道题还是后序遍历，然后在走的过程中统计第一个最大深度的节点值就是答案，因为后序遍历先左后右，所以天然满足了左边的条件，然后深度满足最下的条件。

```go
func findBottomLeftValue(root *TreeNode) int {
    if root.Left == nil && root.Right == nil {
        return root.Val
    }
    maxDepth := 0
    res := 0
    dfs(root, 0, &maxDepth, &res)
    return res
}

func dfs(root *TreeNode, depth int, maxDepth, res *int) {
    if root == nil {
        return
    }
    if root.Left == nil && root.Right == nil {
        if depth > *maxDepth {
            *maxDepth = depth
            *res = root.Val
        }
    }
    dfs(root.Left, depth+1, maxDepth, res)
    dfs(root.Right, depth+1, maxDepth, res)
}
```

Last modification：July 13, 2025

如果觉得我的文章对你有用，请随意赞赏

平衡二叉树 & 对称二叉树 & 二叉树中的最大路径和 & 二叉树的直径 & 另一棵树的子树 & 子结构判断 & 监控二叉树 & 路径总和 & 完全二叉树的节点个数 & 找树左下角的值——DFS

SnowKagura • 2025 年 07 月 09 日

# 平衡二叉树

这个需要左右子树的深度差小于等于1，dfs解决

```go
func isBalanced(root *TreeNode) bool {
    _, balanced := valid(root)
    return balanced
}

func abs(val int) int {
    if val > 0 {
        return val
    }
    return -val
}
```

# 对称二叉树

这个需要左右子树的值相等且左子树的左节点等于右子树的右节点，且左子树的右节点等于右子树的左节点

```go
func isSymmetric(root *TreeNode) bool {
    if root == nil {
        return true
    }
    return dfs(root.Left, root.Right)
}

# 二叉树中的最大路径和

这个需要后序遍历+左右子树和本身节点和的最大值，返回给上层的是单条分支的值，因为不能走回头路

```go
func maxPathSum(root *TreeNode) int {
    res := -1 << 31
    dfs(root, &res)
    return res
}

# 二叉树的直径

类似于二叉树中的最大路径和，只是这里不是节点上的值，而是路径长度

```go
func diameterOfBinaryTree(root *TreeNode) int {
    res := 0
    dfs(root, &res)
    return res
}

# 另一棵树的子树

这个问题其实有点类似于对称二叉树，都是找子树的值，只不过对称的条件和子树相等的条件有点不一样，需要当前节点，左节点，右节点都相等。

# 子结构判断

# 监控二叉树

那么

有了上述规则，我们就能得到最优的解

```go
const (
    NOT_COVERED int = iota
    COVERED
    HAS_CAMERA
)

# 路径总和

这道题自己想出来了，就是遍历根节点到叶子节点的总和是否等于target。

# 完全二叉树的节点个数

这道题最简单的做法是全部遍历一遍，也就是所谓的后序遍历。

然后还有一种做法是利用完全二叉树的性质。

因为完全二叉树只有最底层可能不满，所以我们分别从左子树和右子树开始出发往下。

反之，说明右子树是满二叉树，整个过程就颠倒过来，这样做的时间复杂度只有 $(log_2n)^2$

# 找树左下角的值

平衡二叉树 & 对称二叉树 & 二叉树中的最大路径和 & 二叉树的直径 & 另一棵树的子树 & 子结构判断 & 监控二叉树 & 路径总和 & 完全二叉树的节点个数 & 找树左下角的值——DFS

Leave a Comment Cancel reply
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

纪念

关于git的一些用法总结

linux学习笔记——从零开始搭建web环境

关于js中的模板字符串

关于用CSS格式化表单元素的方法

关于js中的浮点数使用的IEEE754数值标准

纪念

关于css中的盒子模型

二次元

关于css中颜色相关的几种表示方式

平衡二叉树 & 对称二叉树 & 二叉树中的最大路径和 & 二叉树的直径 & 另一棵树的子树 & 子结构判断 & 监控二叉树 & 路径总和 & 完全二叉树的节点个数 & 找树左下角的值——DFS

Leave a Comment Cancel reply 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

平衡二叉树 & 对称二叉树 & 二叉树中的最大路径和 & 二叉树的直径 & 另一棵树的子树 & 子结构判断 & 监控二叉树 & 路径总和 & 完全二叉树的节点个数 & 找树左下角的值——DFS

Leave a Comment Cancel reply
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款