2015年7月3日星期五

LeetCode: Symmetric Tree

Iteration way:
At first, I think of binary tree level traversal to judge the symmetry with two dequeues. To make sure the symmetry of structure, null element is also needed to record.
finish later

Recursive way:
Use DFS to traverse the tree from two directions, one is data->left->right, the other is data->right->left.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * Definition for a binary tree node.
 * 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;
        return DFS(root->left, root->right);
    }
    
    bool DFS(TreeNode* left, TreeNode* right){
        if(left == NULL && right == NULL) return true;
        if(left == NULL || right == NULL) return false;
        if(left->val != right->val) return false;
        return DFS(left->left, right->right) && DFS(left->right, right->left);
        //not necessary
        /*if(left->left!=NULL && right->right!=NULL) 
            return DFS(left->left, right->right);     
        if(left->right!=NULL && right->left!=NULL)
            return DFS(left->right, right->left);*/
        
    }
};



Reference:
dequeue tutorial
http://fisherlei.blogspot.com/2013/01/leetcode-symmetric-tree.html
http://www.cnblogs.com/TenosDoIt/p/3440729.html

没有评论:

发表评论