101. 对称二叉树


给定一个二叉树,检查它是否是镜像对称的。
例如,二叉树 [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 {
    //借鉴org
    public boolean isSymmetric(TreeNode root) {
        if(root==null){
            return true;
        }
        TreeNode left =root.left;
        TreeNode right=root.right;
        return helper(left,right);
    }
    public boolean helper(TreeNode left,TreeNode right) {
        if(left==null&&right==null){
            return true;
        }
        if(left==null||right==null){
            return false;
        }
        if(left.val==right.val){
            return //(left.left.val==right.right.val)&& (left.right.val==right.left.val)
                   //&&
                helper(left.left,right.right)&&helper(left.right,right.left);
        }
        return false;
    }

}
假设树上一共 n 个节点。
时间复杂度:这里遍历了这棵树,渐进时间复杂度为 O(n)
空间复杂度:这里的空间复杂度和递归使用的栈空间有关,这里递归层数不超过 n,故渐进空间复杂度为 O(n)。

文章作者:   future
版权声明:   本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 future !
 上一篇
免费储存每个月10G-图床🛏️ 免费储存每个月10G-图床🛏️
https://portal.qiniu.com/signup?code=1h9i9v7apthzmhttps://portal.qiniu.com/signup?code=1h9i9v7apthzm 测试 okhttp://cdn.top
2020-09-12 future
下一篇 
二叉树的最大深度 二叉树的最大深度
二叉树的最大深度给定一个二叉树,找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明:  叶子节点是指没有子节点的节点。示例:给定二叉树 [3,9,20,null,null,15,7], **  3****   /
2020-09-11 future
  目录