[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 is symmetric:

But the following is not:

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

解题思路:

递归版:

 1 /**
 2  * Definition for a binary tree node.
 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         if (root == nullptr) {
14             return true;
15         }
16         
17         return isSymmetric(root->left, root->right);
18     }
19     
20     bool isSymmetric(TreeNode *left, TreeNode *right) {
21         if (!left && !right) return true;
22         if (!left || !right) return false;
23         
24         return left->val == right->val && 
25                 isSymmetric(left->left, right->right) && 
26                 isSymmetric(left->right, right->left);
27     }
28 };

迭代版:

 1 /**
 2  * Definition for a binary tree node.
 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         if (root == nullptr) return true;
14         stack<TreeNode *> cache;
15         cache.push(root->left);
16         cache.push(root->right);
17         while (!cache.empty()) {
18             auto p = cache.top(); cache.pop();
19             auto q = cache.top(); cache.pop();
20             
21             if (!p && !q) continue;
22             if (!p || !q) return false;
23             if (p->val != q->val) return false;
24             
25             cache.push(p->left); cache.push(q->right);
26             cache.push(p->right); cache.push(q->left);
27         }
28         
29         return true;
30     }
31 };