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
没有评论:
发表评论