Leetcode_solutions/100 - same tree.java at master · rayxcc/Leetcode_solutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

public boolean isSameTree(TreeNode p, TreeNode q) {
    TreeNode nodeOne = p;
    TreeNode nodeTwo = q;
    Stack<TreeNode> stackOne = new Stack<TreeNode>();
    Stack<TreeNode> stackTwo = new Stack<TreeNode>();

    // deal with empty tree
    if ((p == null) && (q == null)) {
    	return true;
    } else if ((p == null) || (q == null)) {
    	return false;
    }

    // use preorder traverse to determine
    while (true) {
    	while ((nodeOne != null) && (nodeTwo != null)) {
    		if (nodeOne.val != nodeTwo.val) {
    			return false;
    		} else {
    			if ((nodeOne.right != null) && (nodeTwo.right != null)) {
    				stackOne.push(nodeOne.right);
    				stackTwo.push(nodeTwo.right);
    			} else if ((nodeOne.right != null) || (nodeTwo.right != null)) { // one has right child while the other not
    				return false;
    			}
    			nodeOne = nodeOne.left;
    			nodeTwo = nodeTwo.left;
    		}
    	}

    	// NOTICE: easy to be wrong about the logic here! - deal with the left child
    	if (((nodeOne == null) && (nodeTwo != null)) || ((nodeOne != null) && (nodeTwo == null)))
    	    return false;

    	if (stackOne.isEmpty() || stackTwo.isEmpty())
    		return true;
    	nodeOne = stackOne.pop();
    	nodeTwo = stackTwo.pop();

    }
}