LeetCode 101-对称二叉树：递归与迭代解法详解

LeetCode 101-对称二叉树：递归与迭代解法详解

引用

CSDN

1.

https://blog.csdn.net/qq_44581505/article/details/139493827

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;
    }
}
  

难点

• 考虑清楚遍历顺序。
• 迭代法中，这里不是层序遍历，而是仅仅通过一个容器来成对存放我们要比较的元素。因此，虽然在这里的解法中使用了队列，实际上，用栈、数组也是可以的。

总结

二叉树问题的遍历顺序很重要！一般来说，递归法更容易实现，因此掌握好“递归三部曲”是很有必要滴 😃。