专栏首页架构说[LeetCode] Symmetric Tree

[LeetCode] Symmetric Tree

1、题目名称

  1. 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).

For example, this binary tree is symmetric:

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

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

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

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 TreeDescription:    // 函数功能、性能等的描述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

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

一颗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个节点进行比较 还有是遍历都(递归方式 还是非递归)记录上下节点位置(父子) 左右节点位置不好记录 (孩子之间)

类似题目:

  1. 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

本文分享自微信公众号 - 架构说(JiaGouS),作者:troy

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2016-04-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 使用虚拟节点改进的一致性哈希算法

    1 作者:@lionets 分析缺点 连接:http://my.oschina.net/lionets/blog/288066 2 作者:@糖拌咸鱼 ...

    程序员小王
  • 数据库如何做到平滑扩容

    为了增加db的并发能力,常见的方案就是对数据进行sharding,也就是常说的分库分表,这个需要在初期对数据规划有一个预期,从而预先分配出足够的库来处理。

    程序员小王
  • leetcode538. 把二叉搜索树转换为累加树

    给定一个二叉搜索树(Binary Search Tree),把它转换成为累加树(Greater

    程序员小王
  • 数据结构(一):二叉树

    二叉树( binary tree )是有限节点集合构成的结构,其结构的递归定义为:

    zhipingChen
  • 算法面试能过几关:咱也不知道,咱也不敢问

    微信公众号“程序员小灰”的作者,具有多年软件行业从业经验,先后在京东金融、摩拜科技从事研发工作,对算法有一定的兴趣和经验。

    用户1682855
  • RadonDB架构解析

    RadonDB在DTCC大会主会场宣布开源了, 一个期待已久的产品终于走进了开源社区。 感谢青云领导层的对技术贡献的情怀。

    [3306 Pai ] 社区
  • Python 刷题笔记:深度优先搜索专题

    今天来接触下专业术语——深度优先搜索算法(英语:Depth-First-Search,DFS)

    TTTEED
  • 树的遍历 Traverse a Tree

    值得注意的是,当删除树中的节点时,删除过程将按照后序遍历的顺序进行。也就是说,当你删除一个节点时,你将首先删除它的左节点和它的右边的节点,然后再删除节点本身。

    爱写bug
  • 重温数据结构:深入理解红黑树

    读完本文你将了解到: 什么是红黑树 黑色高度 红黑树的 5 个特性 红黑树的左旋右旋 指定节点 x 的左旋 右图转成左图 指定节点 y 的右旋左图转成右图 红...

    张拭心 shixinzhang
  • 重温数据结构:理解 B 树、B+ 树特点及使用场景

    B 树就是常说的“B 减树(B- 树)”,又名平衡多路(即不止两个子树)查找树,它和平衡二叉树的不同有这么几点:

    张拭心 shixinzhang

扫码关注云+社区

领取腾讯云代金券