symmetric tree

symmetric tree

Intersting problem

Both preorder travel and postorder travel can work. However, inorder travel does not work.When a node it NULL do not forget add #

 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     bool isSymmetric(TreeNode *root) {
13         string s1 = "";
14         string s2 = "";
15         lfs(root,s1);
16         rfs(root,s2);
17         return s1 == s2;
18     }
19     void lfs( TreeNode* root, string& s ) {
20         if ( !root ) {
21             s += "#";
22             return;
23         }
24         lfs(root->left,s);
25         lfs(root->right,s);
26          s += root->val+'0';
27     }
28     void rfs( TreeNode* root, string& s ) {
29         if ( !root ) {
30             s += "#";
31             return;
32         }
33         rfs(root->right,s);
34         rfs(root->left,s);
35         s += root->val+'0';
36     }
37 };

Easy understand version

 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     bool isSymmetric(TreeNode *root) {
13         return check(root,root);
14     }
15     bool check( TreeNode* r1, TreeNode* r2 ) {
16         if ( !r1 && !r2 ) {
17             return true;
18         }
19         if ( !r1 ) {
20             return false;
21         }
22         if ( !r2 ) {
23             return false;
24         }
25         if ( r1->val != r2->val ) {
26             return false;
27         }
28         if ( !check(r1->left,r2->right) ) {
29             return false;
30         }
31         if ( !check(r1->right,r2->left) ) {
32             return false;
33         }
34         return true;
35     }
36 };

Loading Disqus comments...
Table of Contents