【刷算法】对称的二叉树

Forest10 发布于2019-08-22 18:15 / 3148人阅读

摘要：题目描述请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。分析一般关于二叉树的题目，第一直觉是往递归上面靠，当然了，本题适不适合还暂时不知道。

题目描述

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

分析

一般关于二叉树的题目，第一直觉是往递归上面靠，当然了，本题适不适合还暂时不知道。
所谓镜像二叉树，举个例子

    1                        1
   /                       /  
  2   3    ---镜像--->     3    2
 /  /                        / 
4  5 6                      6 5  4

如上图，这个二叉树就不是对称的。

    1                        1
   /                       /  
  2   2    ---镜像--->     2    2
 /                       /      
4       4                4       4

可以看出来，对于一个节点p来说
如果它的left为空且right为空，则p的左右子树对称；
如果left不为空且right不为空，
如果left的值不等于right的值，p的左右子树不对称
否则递归检查left.left和right.right、left.right和right.left，为什么是这两对节点呢？因为作镜像操作之后，刚好right.right会落到left.left的位置，right.left会落到left.right的位置，所以只要left.left和right.right、left.right和right.left对称即可，后面的可以递归的检查下去。

function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
}
function isSymmetrical(root)
{
    if (root === null)
        return true;
    return check(root.left, root.right);
}
function check(l,  r){
    if(l === null && r === null){
        return true;
    }
    else if(l !== null && r !== null){
        if(l.val !== r.val)
            return false;
        else
            return check(l.left, r.right)&&check(l.right, r.left);
    }
    else{
        return false;
    }
}

云服务器 GPU云服务器二叉树算法最优二叉树算法图二叉树 python二叉树

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/95671.html

使用JavaScript完成二叉树的一些基本操作

摘要：另外，由于篇幅有限，本篇的重点在于二叉树的常见算法以及实现。常见的二叉树实现代码之前写过相关的文章，是关于如何创建及遍历二叉树的，这里不再赘述。同时我们注意到，在二叉树深度比较大的时候，我们光是比较左右是不够的。本篇为复习过程中遇到过的总结，同时也给准备面试的同学一份参考。另外，由于篇幅有限，本篇的重点在于二叉树的常见算法以及实现。常见的二叉树实现代码之前写过相关的文章，是关于如...

YPHP 2019-08-23 12:48 评论0 收藏0
【刷算法】翻转二叉树的递归和非递归解法

摘要：题目描述操作给定的二叉树，将其变翻转为源二叉树的镜像。输入描述解题思路递归版本首先，对数据结构比较了解的话会想到用递归来解决。所谓递归，在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法来自维基百科。题目描述操作给定的二叉树，将其变翻转为源二叉树的镜像。输入描述: 1 1 / ...

wangbjun 2019-08-22 18:06 评论0 收藏0
【刷算法】LeetCode.236-二叉树的最近公共祖先

摘要：给定一个二叉树找到该树中两个指定节点的最近公共祖先。示例输入输出解释节点和节点的最近公共祖先是节点。说明所有节点的值都是唯一的。给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。示例 1: 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出: 3 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。示例 ...

Joonas 2019-08-23 14:31 评论0 收藏0
JavaScript判断对称二叉树

摘要：参考自对称的二叉树公众号秘密花园对称二叉树非对称二叉树实现思路判断根节点相同左子树的右节点和右子树的左节点相同右子树的左节点和左子树的右节点相同步骤模拟一个对称二叉树和非对称二叉树对称二叉树非对称二叉树步骤利用递归实现对称二叉树判断判断两个参考自ConardLi：《对称的二叉树》公众号： code秘密花园对称二叉树: 8 / ...

iliyaku 2019-08-23 18:17 评论0 收藏0