二叉树：属性类题目

树属性题的思维框架

树属性题通常用后序遍历（自底向上，子问题向父节点汇报信息）。

关键问题：每个节点需要从子树获取什么信息，返回什么信息给父节点？

高度与深度

最大深度（LeetCode 104）

int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

最小深度（LeetCode 111）

最小深度 = 到叶子节点的最短路径。注意：单子树节点不是叶子——不能简单地取 min。

int minDepth(TreeNode root) {
    if (root == null) return 0;
    if (root.left == null && root.right == null) return 1;  // 叶子节点
    if (root.left == null) return 1 + minDepth(root.right);  // 只有右子树
    if (root.right == null) return 1 + minDepth(root.left);  // 只有左子树
    return 1 + Math.min(minDepth(root.left), minDepth(root.right));
}

平衡树与直径

平衡二叉树（LeetCode 110）

boolean isBalanced(TreeNode root) {
    return height(root) != -1;
}

// 若平衡返回高度，不平衡返回 -1
int height(TreeNode node) {
    if (node == null) return 0;
    int l = height(node.left);
    if (l == -1) return -1;
    int r = height(node.right);
    if (r == -1) return -1;
    if (Math.abs(l - r) > 1) return -1;
    return 1 + Math.max(l, r);
}

二叉树的直径（LeetCode 543）

直径 = 两个节点间最长路径 = 某节点的左子树高度 + 右子树高度

int maxDiameter = 0;

int diameterOfBinaryTree(TreeNode root) {
    depth(root);
    return maxDiameter;
}

int depth(TreeNode node) {
    if (node == null) return 0;
    int l = depth(node.left), r = depth(node.right);
    maxDiameter = Math.max(maxDiameter, l + r);  // 经过当前节点的直径
    return 1 + Math.max(l, r);
}

路径和

是否存在根到叶的路径和（LeetCode 112）

boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) return false;
    if (root.left == null && root.right == null) return root.val == targetSum;
    return hasPathSum(root.left, targetSum - root.val)
        || hasPathSum(root.right, targetSum - root.val);
}

所有根到叶的路径和（LeetCode 113）

List<List<Integer>> pathSum(TreeNode root, int targetSum) {
    List<List<Integer>> res = new ArrayList<>();
    dfs(root, targetSum, new ArrayList<>(), res);
    return res;
}

void dfs(TreeNode node, int remain, List<Integer> path, List<List<Integer>> res) {
    if (node == null) return;
    path.add(node.val);
    if (node.left == null && node.right == null && remain == node.val) {
        res.add(new ArrayList<>(path));  // 深拷贝
    }
    dfs(node.left, remain - node.val, path, res);
    dfs(node.right, remain - node.val, path, res);
    path.remove(path.size() - 1);  // 回溯
}

任意路径和最大值（LeetCode 124）

路径可以不经过根，但必须连续。

int maxSum = Integer.MIN_VALUE;

int maxPathSum(TreeNode root) {
    oneSideMax(root);
    return maxSum;
}

// 返回从当前节点出发（只能走一侧）的最大贡献值
int oneSideMax(TreeNode node) {
    if (node == null) return 0;
    int l = Math.max(0, oneSideMax(node.left));   // 负的就不要
    int r = Math.max(0, oneSideMax(node.right));
    maxSum = Math.max(maxSum, node.val + l + r);   // 经过当前节点的最大路径
    return node.val + Math.max(l, r);              // 向父节点汇报单侧最大值
}

其他属性题

对称二叉树（LeetCode 101）

boolean isSymmetric(TreeNode root) {
    return isMirror(root.left, root.right);
}

boolean isMirror(TreeNode l, TreeNode r) {
    if (l == null && r == null) return true;
    if (l == null || r == null) return false;
    return l.val == r.val
        && isMirror(l.left, r.right)
        && isMirror(l.right, r.left);
}

翻转二叉树（LeetCode 226）

TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    TreeNode tmp = root.left;
    root.left = invertTree(root.right);
    root.right = invertTree(tmp);
    return root;
}

最低公共祖先（LeetCode 236）

TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left != null && right != null) return root;  // p 和 q 在两侧
    return left != null ? left : right;              // 在同侧
}

规律总结