LeetCode题目:Symmetric Tree

By | 2012 年 10 月 30 日

从根开始,迭代查看左子树和右子树是否是对称的。
其中左子树和右子树对称的条件(均非空条件下)是:

  1. 两个节点值相等
  2. 左节点的左子树和右节点的右子树对称
  3. 左节点的右子树和右节点的左子树对称

这样就很容易写出来递推的算法。



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 not:

    1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.



迭代算法,44ms过大集合

/**
 * 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 *left, TreeNode *right) {
        if(left == NULL) {
            return right == NULL;
        } else {
            if (right == NULL)
                return false;
            else {
                if(left->val != right->val) {
                    return false;
                }
                if(!isSymmetric(left->right,right->left)) {
                    return false;
                }
                if(!isSymmetric(left->left, right->right)) {
                    return false;
                }
                return true;
            }
        }
    }
    bool isSymmetric(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(NULL == root) return true;
        return isSymmetric(root->left,root->right);
    }
};

3 thoughts on “LeetCode题目:Symmetric Tree

  1. 开飞机的小蜗牛
        bool isSymmetric(TreeNode *root) {
            if (! root) return true;
            return comp(root->left, root->right);
        }
        bool comp(TreeNode *l, TreeNode *r) {
            if (! l && ! r) return true;
            if (! l && r || l && ! r) return false;
            if (l->val != r->val) return false;
            return comp(l->left, r->right) && comp(l->right, r->left);
        }
    Reply
  2. woodpig
    bool isSymmetric(TreeNode *root) {
          return isSymmetric(root,root);
    }
    
    bool isSymmetric(TreeNode *left,TreeNode *right) {
    	if(left==NULL&&right==NULL) return true;
    	if(left==NULL||right==NULL)	return false;
    	if((left->val==right->val)&&isSymmetric(left->left,right->right)&&isSymmetric(left->right,right->left))
    			return true;
    	else return false; 
        }
    
    Reply

发表评论

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