文档章节

[LeetCode] Symmetric Tree

一叶舟troy
 一叶舟troy
发布于 2016/04/08 22:57
字数 1504
阅读 46
收藏 0

####1、题目名称 101. Symmetric Tree https://leetcode.com/problems/symmetric-tree/ ####2、题目内容

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

翻译: 给定一颗二叉树,检查它是否与自己的镜像是同一棵树(围绕根节点对称)


####3、解题思路 1

观察规律 从最简单开始别怕麻烦 从1个节点到 三层end
什么样的情况符合条件
    1 如果2个节点都不存在
    2 如果2个节点存在一个 (跟节点值没有关系)
    
	3 如果2个节点都存在并且内容相等为对称

什么样的情况不符合条件

判断一个root是否对称 步骤 1 如果root节点的左右两个节点 p1= root->left p2=root-rgiht 都存在 并且数组相等

步骤 2 满足条件 1 判断P1 和p2 这2个节点是满足对称条件 p3=P1->left 和p4=p2-right p5=p1-right 和p6=p2 -left

步骤 3 满足条件 2 判断 p3 和p4,p5和p6这2个节点是是否对称 重复步骤 1和2

class Solution { public:

   bool check(TreeNode *leftNode, TreeNode *rightNode)
    {   
         //01 判断2个节点是否对称
        //2个节点都为空
        if (leftNode == NULL && rightNode == NULL)
        {    
            return true;
        }
        //2个节点不对称--结构不对称
        if (leftNode == NULL || rightNode == NULL)
        {    
            return false;
        }
        //2个节点不对称--内容不相等
        if(leftNode->val != rightNode->val)
        {
            return false;
        }
        //02 左右节点的之树也是对称的
        return  check(leftNode->left, rightNode->right) && 
                check(leftNode->right, rightNode->left);
    }

/*************************************************
Function: 101. Symmetric Tree
Description:    // 函数功能、性能等的描述
Input:          // 输入参数说明,包括每个参数的作
              // 用、取值说明及参数间关系。
Output:         // 对输出参数的说明。
Return:         // 函数返回值的说明
Others:     troy 2016.4.7
*************************************************/
bool isSymmetric(TreeNode* root) 
{

    if (root == NULL)
    {  
        return true;
    }
        
    return check(root->left, root->right);
}

};

####4、解题思路 2
自己大脑是如何思考的 上面case注意

1 /
2 2 / \ /
3 4 4 3

第一次对比: 2和2 节点 符合条件 第二次对比:3和3节点 符合条件 第三次对比:4和4节点 符合条件

第四次对比:NULl NULL 符合条件 第五次对比:NULl NULL 符合条件

问题来了 轨迹 2 2 3 4 4 3 好像跟树的层次遍历顺序类似 仔细对比一下 正确顺序应该是 1 2 2 3 4 4 3 节点3和4 有通过根节点 不是 3 和3 属于不相同的节点 一个队列是解决不了这问题的就用2个队列

两个队列的出队顺序 root节点左队列A: 2 3 4 NULL NULL root节点右队列 B :2 3 4 NULL NULL

1 /
2 2 \
3 3

第一次对比: 2和2 节点 符合条件 第二次对比:3和 Null节点 不对称 退出

注意:如果节点是NUL也需要记录下来 ,就是这么死板 人一眼看出来,电脑记录不下来

1 节点左队列 A: 2 NULL
1 节点右队列 B :2 3

实现步骤: 步骤 1 构造两个队列 leftQ,rightQ 分别表示左子树遍历顺序 右子树遍历顺序 步骤 2 按照层次遍历 方法 如果2个队列都不为空 然后比较front 连个节点 什么样的情况不符合条件 结构和内容都不对称 步骤 3 重复步骤2 直到结束,如果方向2个队列还有剩余为false

/************************************************* Function: 101. Symmetric Tree Description: 是否对称 Input: root Output:
Return: true --对称 false--不对称 Others: troy 2016.4.7 *************************************************/ bool isSymmetric2(TreeNode *root) { //如果root为null 直接返回 if(root==NULL) { return true;
}

queue<TreeNode*> leftQ;//leftQ  保存左子树遍历顺序
queue<TreeNode*> rightQ;//rightQ 保存右子树遍历顺序

leftQ.push(root->left); 
rightQ.push(root->right);
       
TreeNode* l;
TreeNode* r;
while(!leftQ.empty() && !rightQ.empty())
{
    l = leftQ.front();
    leftQ.pop();
    r = rightQ.front();
    rightQ.pop();
    
    if(l == NULL && r == NULL) continue;//上面算法如果NULL 返回true 为叶子结点 继续遍历
    if(l == NULL || r == NULL) return false;//结构不对称
    if(l->val != r->val) return false;//数值不对称
   
   //注意如队列顺序 观察出来的 3=3  4 =4 
    leftQ.push(l->left);//左 3 右 4
    leftQ.push(l->right);
    rightQ.push(r->right);//右 3 左4 
    rightQ.push(r->left);
}

//如果还有剩余说明不结构不对称 例如 root只有一个
if(!leftQ.empty() || !rightQ.empty())
{
    return false;
} 
return true;

} ####5、解题思路 3

  • [x] 一颗tree 我按照一定顺序遍历完毕,然后观察规律 这个方法不可取 因为存储结构是二叉树 不是数组即使有规律NULL无法完成保存下来 不可以

  • [x] 一颗tree是对称树 那么左右子树遍历顺序结果是一样的

    1 /
    2 2 / \ /
    3 4 4 3

1 左节点中须遍历顺序 3 2 4 1 右节点中队列 B : 2 4 3 不可以

1 左节点后须遍历顺序 3 4 3
1 右节点后须遍历顺序 : 3 4 2 不可以

1 左节点中须遍历顺序 3 4 2
1 右节点后须遍历顺序 : 3 4 2 可以

缺点:必须完全遍历完毕才可以知道 遍历过程中无法比较

####6、 测试用例

Your input [1,2,2,#,#,3] Your answer false Expected answer false Runtime: 0 ms

####7、 总结 如果没有推理 ,记住结论 情况一边就仍然不会 难点: 假如i,j2个节点 判断是否对称很容易 内容一样 如果摆脱tree这么多层次位置,集中到2个节点上进行比较 手工去演示过程 最直接解题思路 必须要完整去演示过程 如果演示不过 说明思路有问题。 遇到问题:

  • [ ] book 上说遍历(先,中,后) 都是参数都是一个节点,现在变成2个节点了 不知道该如何办了 对称 肯定是2个节点进行比较

  • [ ] 还有是遍历都(递归方式 还是非递归)记录上下节点位置(父子) 左右节点位置不好记录 (孩子之间)

类似题目: 104. Maximum Depth of Binary Tree Next challenges: (M) Convert Sorted List to Binary Search Tree
(M) Graph Valid Tree (E) Closest Binary Search Tree Value

© 著作权归作者所有

一叶舟troy
粉丝 10
博文 27
码字总数 24336
作品 0
程序员
私信 提问
加载中

评论(1)

一叶舟troy
一叶舟troy 博主
原文是的Markdown编辑器写的
印象笔记无法分享格式上可能有点乱
[LeetCode] Symmetric Tree 判断对称树

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree is symmetric: 1/ 2 2/ / 3 4 4 3 But the following is......

机器的心脏
2017/12/11
0
0
LeetCode:Symmetric Tree - 判断二叉树是否对称

1、题目名称 Symmetric Tree(判断二叉树是否对称) 2、题目地址 https://leetcode.com/problems/symmetric-tree/ 3、题目内容 英文:Given a binary tree, check whether it is a mirror o...

北风其凉
2015/08/13
1K
0
LeetCode 101. Symmetric Tree (对称树)

原题 Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree is symmetric: But the following is not: Referen......

dby_freedom
2018/12/03
0
0
LeetCode 攻略 - 2019 年 6 月汇总

Create by jsliang on 2019-06-28 09:03:23 Recently revised in 2019-06-28 14:56:36 一 目录 不折腾的前端,和咸鱼有什么区别 目录 一 目录 二 前言 三 汇总  3.1 已攻略  3.2 Function ...

jsliang
06/28
0
0
Leetcode 二叉树解题报告

1. Binary Tree Preorder Traversal Description Given a binary tree, return the preorder traversal of its nodes' values. Example: Input: [1,null,2,3] 1 2 / 3 Output: [1,2,3] Analy......

BookThief
2018/07/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周六乱弹 —— 如果是个帅小伙你愿意和他出去吗

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 小小编辑推荐:《Ghost 》游戏《死亡搁浅》原声 《Ghost 》游戏(《死亡搁浅》原声) - Au/Ra / Alan Walker 手机党少年们想听歌,请使劲儿戳...

小小编辑
27分钟前
27
3
java通过ServerSocket与Socket实现通信

首先说一下ServerSocket与Socket. 1.ServerSocket ServerSocket是用来监听客户端Socket连接的类,如果没有连接会一直处于等待状态. ServetSocket有三个构造方法: (1) ServerSocket(int port);...

Blueeeeeee
今天
6
0
用 Sphinx 搭建博客时,如何自定义插件?

之前有不少同学看过我的个人博客(http://python-online.cn),也根据我写的教程完成了自己个人站点的搭建。 点此:使用 Python 30分钟 教你快速搭建一个博客 为防有的同学不清楚 Sphinx ,这...

王炳明
昨天
5
0
黑客之道-40本书籍助你快速入门黑客技术免费下载

场景 黑客是一个中文词语,皆源自英文hacker,随着灰鸽子的出现,灰鸽子成为了很多假借黑客名义控制他人电脑的黑客技术,于是出现了“骇客”与"黑客"分家。2012年电影频道节目中心出品的电影...

badaoliumang
昨天
16
0
很遗憾,没有一篇文章能讲清楚线程的生命周期!

(手机横屏看源码更方便) 注:java源码分析部分如无特殊说明均基于 java8 版本。 简介 大家都知道线程是有生命周期,但是彤哥可以认真负责地告诉你网上几乎没有一篇文章讲得是完全正确的。 ...

彤哥读源码
昨天
19
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部