二叉树

解决关于二叉树的算法题通常可以通过递归或迭代的方式来处理。二叉树的问题大多可以归类为以下几种类型：

1. 遍历问题：前序（根-左-右）、中序（左-根-右）、后序（左-右-根）和层次遍历。
2. 属性问题：比如计算树的高度、判断二叉树是否平衡等。
3. 路径问题：比如寻找从根到叶子的路径之和等。
4. 结构问题：比如翻转二叉树、合并二叉树等。
5. 动态规划问题：比如二叉树中的最大路径和。

下面我会给出几个 Go 语言的代码实例来说明这些通用思路。

1. 遍历问题 - 中序遍历

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

func inorderTraversal(root *TreeNode) []int {
    var res []int
    var inorder func(node *TreeNode)
    inorder = func(node *TreeNode) {
        if node == nil {
            return
        }
        inorder(node.Left)
        res = append(res, node.Val)
        inorder(node.Right)
    }
    inorder(root)
    return res
}

2. 属性问题 - 计算树的高度

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    leftDepth := maxDepth(root.Left)
    rightDepth := maxDepth(root.Right)
    if leftDepth > rightDepth {
        return leftDepth + 1
    }
    return rightDepth + 1
}

3. 路径问题 - 根到叶子的路径之和

func hasPathSum(root *TreeNode, sum int) bool {
    if root == nil {
        return false
    }
    if root.Left == nil && root.Right == nil {
        return sum == root.Val
    }
    return hasPathSum(root.Left, sum-root.Val) || hasPathSum(root.Right, sum-root.Val)
}

4. 结构问题 - 翻转二叉树

func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    root.Left, root.Right = invertTree(root.Right), invertTree(root.Left)
    return root
}

5. 动态规划问题 - 二叉树中的最大路径和

func maxPathSum(root *TreeNode) int {
    maxSum := math.MinInt32
    var maxGain func(node *TreeNode) int
    maxGain = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        leftGain := max(0, maxGain(node.Left))
        rightGain := max(0, maxGain(node.Right))
        priceNewpath := node.Val + leftGain + rightGain
        maxSum = max(maxSum, priceNewpath)
        return node.Val + max(leftGain, rightGain)
    }
    maxGain(root)
    return maxSum
}

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

在解决二叉树的问题时，递归是一种非常自然和强大的方法，因为二叉树本身的结构就是递归定义的。迭代方法通常需要使用栈来模拟递归过程。在实际编码时，应该选择最适合问题的方法。