LeetCodeJava/LeetCode0236.java at master · zyt153/LeetCodeJava · 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
/* Lowest Common Ancestor of a Binary Tree
 * Input: p = 5, q = 4,
 *         3
          / \
         5   1
        / \ / \
       6  2 0  8
         / \
        7   4
 * Output: 5
 * */

import com.sun.source.tree.Tree;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class LeetCode0236 {
    public static int index = 0;
    public static int[] TREE_VALUE = new int[]{3, 5, 6, 0, 0, 2, 7, 0, 0, 4, 0, 0, 1, 0, 0, 0, 8, 0, 0};

    public static void main(String args[]) {
        TreeNode root = new TreeNode();
        root = TreeNode.createTree(root, index, TREE_VALUE);
        TreeNode p = root.left;
        TreeNode q = root.left.right.right;
        System.out.println(lowestCommonAncestor(root, p, q).val);
    }

    static Map<Integer, TreeNode> parent = new HashMap<Integer, TreeNode>();
    static Set<Integer> visited = new HashSet<Integer>();

    public static void dfs(TreeNode root){
        if(root.left != null){
            parent.put(root.left.val, root);
            dfs(root.left);
        }
        if(root.right != null){
            parent.put(root.right.val, root);
            dfs(root.right);
        }
    }

    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root);
        while(p != null){
            visited.add(p.val);
            p = parent.get(p.val);
        }
        while(q!=null){
            if(visited.contains(q.val))
                return q;
            q = parent.get(q.val);
        }
        return null;
    }
}