import java.util.Stack;
/**
* Source : https://oj.leetcode.com/problems/same-tree/
*
*
* Given two binary trees, write a function to check if they are equal or not.
*
* Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
*/
public class SameTree {
/**
* 比较两个是否相同
* 如果两棵树都为空，相同
* 如果只有一棵树为空，不相同
* 如果两棵树都不为空，则根节点相同，递归判断左右节点也要相同
*
* @param tree1
* @param tree2
* @return
*/
public boolean isSame (TreeNode tree1, TreeNode tree2) {
if (tree1 == null && tree2 == null) {
return true;
}
if ((tree1 == null && tree2 != null) || (tree1 != null && tree2 == null)) {
return false;
}
if (tree1.value != tree2.value) {
return false;
}
return isSame(tree1.leftChild, tree2.leftChild) && isSame(tree1.rightChild, tree2.rightChild);
}
/**
* 不使用递归，使用循环判断
*
* @param tree1
* @param tree2
* @return
*/
public boolean isSameByIterator (TreeNode tree1, TreeNode tree2) {
Stack<TreeNode> stack1 = new Stack<TreeNode>();
Stack<TreeNode> stack2 = new Stack<TreeNode>();
stack1.push(tree1);
stack2.push(tree2);
while (stack1.size() > 0 && stack2.size() > 0) {
TreeNode node1 = stack1.pop();
TreeNode node2 = stack2.pop();
if (node1 == null && node2 == null) {
continue;
}
if ((node1 == null && node2 != null) || (node1 != null && node2 == null)) {
return false;
}
if (node1.value != node2.value) {
return false;
}
stack1.push(node1.leftChild);
stack1.push(node1.rightChild);
stack2.push(node2.leftChild);
stack2.push(node2.rightChild);
}
return true;
}
public TreeNode createTree (char[] treeArr) {
TreeNode[] tree = new TreeNode[treeArr.length];
for (int i = 0; i < treeArr.length; i++) {
if (treeArr[i] == '#') {
tree[i] = null;
continue;
}
tree[i] = new TreeNode(treeArr[i]-'0');
}
int pos = 0;
for (int i = 0; i < treeArr.length && pos < treeArr.length-1; i++) {
if (tree[i] != null) {
tree[i].leftChild = tree[++pos];
if (pos < treeArr.length-1) {
tree[i].rightChild = tree[++pos];
}
}
}
return tree[0];
}
private class TreeNode {
TreeNode leftChild;
TreeNode rightChild;
int value;
public TreeNode(int value) {
this.value = value;
}
public TreeNode() {
}
}
public static void main(String[] args) {
SameTree sameTree = new SameTree();
char[] tree1 = new char[]{'1','2','3','#','#','4'};
char[] tree2 = new char[]{'1','2','3','#','#','4'};
char[] tree3 = new char[]{'1','2','3','2','#','4'};
System.out.println(sameTree.isSame(sameTree.createTree(tree1), sameTree.createTree(tree2)) + "---true");
System.out.println(sameTree.isSame(sameTree.createTree(tree1), sameTree.createTree(tree3)) + "---false");
System.out.println(sameTree.isSameByIterator(sameTree.createTree(tree1), sameTree.createTree(tree2)) + "---true");
System.out.println(sameTree.isSameByIterator(sameTree.createTree(tree1), sameTree.createTree(tree3)) + "---false");
}
}