2014
11-10

# Symmetric Tree[LeetCode]对称二叉树

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

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

public class SymmetricTree {
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public boolean isSymmetric(TreeNode root) {
if(root == null) return true;
return isSymmetric(root.left, root.right);
}
public boolean isSymmetric(TreeNode leftNode, TreeNode rightNode){
if(leftNode == null && rightNode == null ) return true;
if(leftNode == null || rightNode == null) return false;
if(leftNode.val != rightNode.val) return  false;
boolean isLeft = isSymmetric(leftNode.left, rightNode.right);
boolean isRight = isSymmetric(leftNode.right, rightNode.left);
return isLeft && isRight;
}

public static void main(String args[]){
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(2);
root.left.left = new TreeNode(3);
root.left.right = new TreeNode(4);
root.right.left = new TreeNode(4);
root.right.right = new TreeNode(3);
System.out.println(new SymmetricTree().isSymmetric(root));
System.out.println(new SymmetricTree().isSymmetricIter(root));
}
}

方法二 迭代 Iteratively

    1
/ \
2   2
/   /
3   3

public boolean isSymmetricIter(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;
}

1. L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-1]）这个地方也也有笔误
应改为L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-2]）

2. 我还有个问题想请教一下，就是感觉对于新手来说，递归理解起来有些困难，不知有没有什么好的方法或者什么好的建议？

3. #include <cstdio>
#include <cstring>

const int MAXSIZE=256;
//char store[MAXSIZE];
char str1[MAXSIZE];
/*
void init(char *store) {
int i;
store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
for(i=’F';i<=’Z';++i) store =i-5;
}
*/
int main() {
//freopen("input.txt","r",stdin);
//init(store);
char *p;
while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
if(p=fgets(str1,MAXSIZE,stdin)) {
for(;*p;++p) {
//*p=store[*p]
if(*p<’A’ || *p>’Z') continue;
if(*p>’E') *p=*p-5;
else *p=*p+21;
}
printf("%s",str1);
}
fgets(str1,MAXSIZE,stdin);
}
return 0;
}