首页 > 代码库 > leetcode:Symmetric Tree
leetcode:Symmetric Tree
一、 题目
给一个二叉树,判断这个树是不是镜像的(对称的)。
例子: 1
/ \
2 2
/ \ / \
3 4 4 3
但是这个就不是: 1
/ \
2 2
\ \
3 3
二、 分析
1、递归
从根开始,迭代查看左子树和右子树是否是对称的。
其中左子树和右子树对称的条件(均非空条件下)是:
1>两个节点值相等
2>左节点的左子树和右节点的右子树对称
3>左节点的右子树和右节点的左子树对称
2、非递归
使用非递归时,我们可以创建两个队列,将根节点的左右子树分别入队,入队的同时比较,发现对称位置的节点值不等,则返回false;
1> 根节点的左右子树入队
2> 队列出队
3> 如果值相等,则4,否则返回false
4> 将当前左节点左子树和当前右节点的右子树入队,如果其中只要有一个为空,则返回false
5> 将当前右节点左子树和当前左节点的右子树入队,如果其中只要有一个为空,则返回false
6> 最后,判断两个队列是否同时为空,是,则返回true,否则返回false
递归:
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool isSymmetric(TreeNode *Lroot,TreeNode *Rroot) { if(Lroot==NULL) return Rroot==NULL; else { if(Rroot==NULL) return false; if(Lroot->val!=Rroot->val) return false; if(!isSymmetric(Lroot->right,Rroot->left)) return false; if(!isSymmetric(Lroot->left,Rroot->right)) return false; return true; } } bool isSymmetric(TreeNode *root) { if(root==NULL) return true; TreeNode *Rroot; TreeNode *Lroot; Rroot = root->right; Lroot = root->left; return isSymmetric(Lroot,Rroot); } };
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool isSymmetric(TreeNode *root) { if (! root) return true; return compare(root->left, root->right); } bool compare(TreeNode *Lroot, TreeNode *Rroot) { if (Lroot!=NULL && Rroot!=NULL) return true; if (Lroot!=NULL && Rroot==NULL || Lroot==NULL && Rroot!=NULL) return false; if (Lroot->val != Rroot->val) return false; return compare(Lroot->left, Rroot->right) && compare(Lroot->right, Rroot->left); } };
非递归:
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: bool isSymmetric(TreeNode *root) { if(root==NULL) return true; queue<TreeNode *> Lque; queue<TreeNode *> Rque; if(root->left) Lque.push(root->left); if(root->right) Rque.push(root->right); while(!Lque.empty()&&!Rque.empty()){ TreeNode *ql = Lque.front(); TreeNode *qr = Rque.front(); Lque.pop(); Rque.pop(); if(ql->val == qr->val){ if(ql->left&&qr->right){ Lque.push(ql->left); Rque.push(qr->right); } else if(ql->left||qr->right) return false; if(qr->left&&ql->right){ Lque.push(qr->left); Rque.push(ql->right); } else if(qr->left||ql->right) return false; } else return false; } if(Lque.empty() && Rque.empty()) return true; else return false; } };
leetcode:Symmetric Tree
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。