2014
11-19

# LeetCode-Symmetric Tree[二叉树]

### 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.

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

OJ’s Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.

Here’s an example:

   1
/ \
2   3
/
4
\
5


The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

// LeetCode, Symmetric Tree
// 递归版，时间复杂度O(n)，空间复杂度O(logn)
class Solution {
public:
bool isSymmetric(TreeNode *root) {
return root ? isSymmetric(root->left, root->right) : true;
}
bool isSymmetric(TreeNode *left, TreeNode *right) {
if (!left && !right) return true;   // 终止条件
if (!left || !right) return false;  // 终止条件
return left->val == right->val      // 三方合并
&& isSymmetric(left->left, right->right)
&& isSymmetric(left->right, right->left);
}
};


// LeetCode, Symmetric Tree
// 迭代版，时间复杂度O(n)，空间复杂度O(logn)
class Solution {
public:
bool isSymmetric (TreeNode* root) {
if (!root) return true;

stack<TreeNode*> s;
s.push(root->left);
s.push(root->right);

while (!s.empty ()) {
auto p = s.top (); s.pop();
auto q = s.top (); s.pop();

if (!p && !q) continue;
if (!p || !q) return false;
if (p->val != q->val) return false;

s.push(p->left);
s.push(q->right);

s.push(p->right);
s.push(q->left);
}

return true;
}
};


Java代码:

/**
* Definition for binary tree
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null) return true;
Stack<TreeNode> leftStack = new Stack<TreeNode>();
Stack<TreeNode> rightStack = new Stack<TreeNode>();

leftStack.push(root.left);
rightStack.push(root.right);

while (leftStack.size() > 0 && rightStack.size() > 0){
TreeNode left = leftStack.pop();
TreeNode right = rightStack.pop();
if(left == null && right == null) continue;
if(left == null || right == null) return false;
if(left.val == right.val){
leftStack.push(left.right);
leftStack.push(left.left);
rightStack.push(right.left);
rightStack.push(right.right);
}else return false;
}
return true;
}
}

Same Tree

1. #include <cstdio>

int main() {