leetcode/Solution_100.java at master · zyflool/leetcode · 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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
/*
100. 相同的树
给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1:
输入:       1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]
输出: true

示例 2:
输入:      1          1
          /           \
         2             2

        [1,2],     [1,null,2]
输出: false

示例 3:
输入:       1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]
输出: false
 */

class Solution {
    public static void main(String[] args) {
        TreeNode[] n = new TreeNode[] {
                new TreeNode(1), new TreeNode(2), new TreeNode(1),
                new TreeNode(1), new TreeNode(1), new TreeNode(2)
        };
        n[0].left = n[1];
        n[0].right = n[2];
        n[3].left = n[4];
        n[3].right = n[5];
        Solution solution = new Solution();
        System.out.println(solution.isSameTree(n[0],n[3]));
    }

    private boolean answer = true;

    public boolean isSameTree(TreeNode p, TreeNode q) {
        solve(p,q);
        return answer;
    }

    private void solve ( TreeNode p, TreeNode q ) {
        if (p == null && q == null) {
            return ;
        } else if (p != null && q == null) {
            answer = false;
            return;
        } else if (q != null && p == null)  {
            answer = false;
            return ;
        }
        if ( !answer )
            return ;
        if (p.val != q.val) {
            answer = false;
            return ;
        }

        if (p.left != null && q.left != null)
            isSameTree(p.left, q.left);

        if (p.right != null && q.right != null)
            isSameTree(p.right, q.right);

        if ((p.right == null && q.right != null) ||
                (p.right != null && q.right == null) ||
                (p.left != null && q.left == null) ||
                (p.left == null && q.left != null) ) {
            answer = false;
            return ;
        }
    }

}