LeetCode 解题思路 20（Hot 100）

解题思路：

1. 递归定义对称性： 若两棵子树镜像对称，需满足：

• 当前节点值相等；
• 左子树的左节点与右子树的右节点对称；
• 左子树的右节点与右子树的左节点对称。

2. 终止条件：

• 两个节点均为空 → 对称；
• 一个节点为空，另一个非空 → 不对称；
• 节点值不等 → 不对称。

Java代码：

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root.left, root.right);
    }

    private boolean check(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        if (left.val != right.val) return false; 
        return check(left.left, right.right) && check(left.right, right.left);
    }
}

复杂度分析：

• 时间复杂度： O(n)，每个节点最多被访问一次。
• 空间复杂度： O(h)，h为树的高度。最坏情况（链表状树）：O(n)，最优情况（平衡树）：O(log n)。
  

解题思路：

1. 递归计算子树高度： 对于每个节点，递归计算其左子树和右子树的高度。
2. 更新最长路径： 在计算当前节点的子树高度时，利用左子树和右子树的高度之和（left + right + 1）来更新全局变量 res。此值表示以当前节点为中间节点的最长路径的节点数。
3. 返回子树高度： 当前节点的子树高度为左、右子树高度的较大值加1，用于上层节点的路径计算。
4. 结果转换： 由于树的直径是边的数量，而 res 记录的是节点数，最终结果需返回 res - 1。

Java代码：

class Solution {
    int res = 1;
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return res - 1;
    }
    private int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = dfs(node.left);
        int right = dfs(node.right);
        res = Math.max(res, left + right + 1);
        return Math.max(left, right) + 1;
    }
}

复杂度分析：

• 时间复杂度： O(n)。每个节点仅被访问一次，递归调用的总次数为 n（n 为节点数）。
• 空间复杂度： O(h)。h 为树的高度，由递归调用栈的深度决定。最坏情况下（树退化为链表），空间复杂度为 O(n)；平均情况下为 O(log n)。