代码随想录-二叉树 | 101对称二叉树

LeetCode 101-对称二叉树
- 解题思路
- 代码
- 难点
- 总结

LeetCode 101-对称二叉树

题目链接
代码随想录

题目描述

给你一个二叉树的根节点 root ，检查它是否轴对称。

解题思路

判断：

同时遍历并比较根节点的左、右子树。
要比较外侧和里侧节点，两个子树的遍历顺序应该为：一个是左右根，另一个是右左根。都可以理解为是后序遍历。

可用递归法、迭代法。
递归法：
1. 确定递归函数的参数和返回值：参数是两个树，即根节点的左孩子和右孩子。返回值是bool类型。
2. 确定终止条件
  - 首先考虑两个节点为空的情况，避免后面比较数值时操作空节点：左、右节点有且仅有一个为空，不对称，return false，左、右节点都为空，对称，return true。
  - 其次考虑两个节点都不为空：比较节点数值，若不同，return false。
3. 确定单层递归的逻辑：即，处理左右节点都不为空，且数值相同的情况。
  - 比较外侧是否对称
  - 比较内侧是否对称
  - 若有一侧不对称，return false；否则 return true
迭代法(不是层序遍历)：
- 使用队列，判断根节点的左子树和右子树的内外侧是否相等。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

递归法

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return compare(root.left, root.right);

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

迭代法

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        //使用普通队列
        Queue<TreeNode> deque = new LinkedList<>();
        deque.offer(root.left);
        deque.offer(root.right);

        while(!deque.isEmpty()){
            TreeNode left = deque.poll();
            TreeNode right = deque.poll();
            if (left == null && right == null) continue; 
            if (left == null || right == null || left.val != right.val) return false;
            //如果左右节点相等，继续往下判断
            deque.offer(left.left);
            deque.offer(right.right);
            deque.offer(left.right);
            deque.offer(right.left);
        }
        return true;
    }
}