【Leetcode】101. 对称二叉树

╰半夏微凉° 2022-03-07 09:40 171阅读 0赞

# 题目 #

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 \[1,2,2,3,4,4,3\] 是对称的。

1
       / \
      2   2
     / \ / \
    3  4 4  3

但是下面这个 \[1,2,2,null,3,null,3\] 则不是镜像对称的:

1
       / \
      2   2
       \   \
       3    3

# 题解 #

还记得我们上几次说过，二叉树的题目，大多数可以用递归解决。  
而递归主要确定两点：

*  递归的子问题是什么;
 *  递归的结束条件是什么

这个题这两点都不难找到,直接看代码吧。

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public boolean isSymmetric(TreeNode root) {
            return root == null || isSymmetricHelp(root.left, root.right);
        }
    
        private boolean isSymmetricHelp(TreeNode left, TreeNode right) {
            if (left == null || right == null)
                return left == right;
            if (left.val != right.val)
                return false;
            return isSymmetricHelp(left.left, right.right) && isSymmetricHelp(left.right, right.left);
        }
    }

这个题目还要求用非递归的方式去解.

一种很直观的想法就是利用层序遍历，看它是不是对称的.

入队顺序依次是, 左子树的左儿子,右子树的右儿子  
左子树的右儿子,右子树左右儿子。  
这样出队的时候两两检查是不是对称。

public boolean isSymmetric(TreeNode root) {
            Queue<TreeNode> q = new LinkedList<TreeNode>();
            if(root == null) return true;
            q.add(root.left);
            q.add(root.right);
            while(!q.isEmpty()){
                TreeNode left = q.poll();
                TreeNode right = q.poll();
                // 叶子节点.
                if(left== null&& right == null) continue;
                // 其中一个为null 肯定不是
                if(left == null ^ right == null) return false;
                // 值不相同
                if(left.val != right.val) return false;
    
                q.add(left.left);
                q.add(right.right);
                q.add(left.right);
                q.add(right.left);            
            }
            return true;
        }

# 热门阅读 #

*  [技术文章汇总][Link 1]
 *  [【Leetcode】100. 相同的树][Leetcode_100.]
 *  [【Leetcode】98. 验证二叉搜索树][Leetcode_98.]
 *  [【Leetcode】95~96 不同的二叉搜索树][Leetcode_95_96]

![Leetcode名企之路][Leetcode]

[Link 1]: https://mp.weixin.qq.com/s/DhfXloRLmZnm786jNPK90Q
[Leetcode_100.]: https://mp.weixin.qq.com/s/r0eJKHJjTQq9KG93ta6CWA
[Leetcode_98.]: https://mp.weixin.qq.com/s/5XJ3grHlZSQIThW3NlVz-w
[Leetcode_95_96]: https://mp.weixin.qq.com/s/Wg_7MBJbEvou-rQaEW7spw
[Leetcode]: /images/20220307/e598459398014cd181a3fb5944c5a72c.png