Leetcode-101-Symmetric-Tree

🧠 思路总结

递归三部曲:

1. 确定递归函数的参数和返回值
2. 确定终止条件

• 节点为空的情况有：
  • 左节点为空，右节点不为空，不对称，return false
  • 左不为空，右为空，不对称 return false
  • 左右都为空，对称，返回true
• 此时已经排除掉了节点为空的情况，那么剩下的就是左右节点不为空：
  左右都不为空，比较节点数值，不相同就return false

3. 确定单层递归的逻辑

• 比较二叉树外侧是否对称:
  • 传入的是左节点的左孩子，右节点的右孩子。
• 比较内侧是否对称：
  • 传入左节点的右孩子，右节点的左孩子。
    如果左右都对称就返回true，有一侧不对称就返回false。

❗ 易错点 / 小坑

遍历方式：左子树左右中，右子树右左中，所以我把这个遍历顺序也称之为“后序遍历”

✅ 代码（Java）

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

    private boolean compare(TreeNode left, TreeNode right) {
        if (left == null && right != null) {
            return false;
        } else if (left != null && right == null) {
            return false;
        } else if (left == null && right == null) {
            return true;
        } else if (left.val != right.val) {
            return false;
        } else {
            boolean outside = compare(left.left, right.right);
            boolean inside = compare(left.right, right.left);
            boolean isSame = outside && inside;
            return isSame;
        }
    }
}