对称二叉树分析

你猜 阅读:380 2020-10-22 16:35:20 评论: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

解:这道题乍一看,想法是用栈,对根节点的左右两颗子树,先对左子树后序遍历分别入栈,后对右子树前序遍历出栈,如果有节点和栈顶不相同或最后栈不为空,则是不对称的,但是这种方法,在左右子树某个节点为空时,出现错误, 如

  1

  /      \

   2        2

  /         /

1         1

这种情况下,上述判断方法就是错的,

以下方法可以

bool isSymmetric(TreeNode *root) { 
    return isMirror(root, root); 
} 
bool isMirror(TreeNode *t1, TreeNode *t2) { 
    if (t1 == null && t2 == null) return true; 
    if (t1 == null || t2 == null) return false; 
    return (t1->val == t2->val) 
        && isMirror(t1->right, t2->left) 
        && isMirror(t1->left, t2->right); 
}

 

声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

发表评论
搜索
KIKK导航

KIKK导航

排行榜
关注我们

一个IT知识分享的公众号