CY-Left

LeetCode基本功底

[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 [1,2,2,3,4,4,3] is symmetric:

比如说,二进制树为 [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

注意: 递归和迭代是加分点。


两种方式都列举如下

下面有两个私有方法,都是能递归法,解题的,第二种方式略好,第一种容易理解。

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return isRight(root->left, root->right);
    }
private:
    bool isRight(TreeNode* l, TreeNode* r){
        if(!l && !r) return true;
        if(!l&&r || l&&!r) return false;
        // if (!p || !q) return q == p;
        if(l->val != r->val) return false;
        return isRight(l->left, r->right) && isRight(l->right, r->left);
    }
    bool dfs(TreeNode *left, TreeNode* right){
        if(left==NULL || right ==NULL){
            return left==right;
        }
        return (left->val==right->val) && dfs(left->left,right->right) && dfs(left->right,right->left);
    }
};

本文虽拙,却也系作者劳动,转载还请保留本文链接: http://cyleft.com/?p=478



Have any Question or Comment?

发表评论

电子邮件地址不会被公开。 必填项已用*标注