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
    
      stack1 = new Stack
     
      ();        Stack
      
        stack2 = new Stack
       
        ();        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");    }}