二叉树最近公共祖先

给定一颗二叉树以及两个节点，查找两个节点最近的公共祖先，有可能公共祖先是两个节点中的其中一个
比如给定D,E两个节点，其最近的公共祖先为B

非递归方式
层次遍历找到两个节点，遍历过程中，将每个节点以及它的父节点放到Map中存起来，需要使用到队列，Map，Set
1.根节点入队，并且根节点的父节点为null
2.Map中没有两个给定节点层次遍历
3.队列出队节点，该节点如果存在左右节点，将左右节点分别入队，并且将子节点与父节点存入Map
4.循环2
5.两个节点均找到，将其中一个节点的祖先节点放入Set
6.寻找另一个节点的祖先节点，看看是否在Set中，如果存在返回该祖先节点

 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Map<TreeNode, TreeNode> parentMap = new HashMap<>();
        Queue<TreeNode> queue = new LinkedList<>();
        parentMap.put(root, null);
        queue.add(root);
        while (!parentMap.containsKey(p) || !parentMap.containsKey(q)) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                parentMap.put(node.left, node);
                queue.add(node.left);
            }
            if (node.right != null) {
                parentMap.put(node.right, node);
                queue.add(node.right);
            }
        }
        Set<TreeNode> ancestors = new HashSet<>();
        while (p != null) {
            ancestors.add(p);
            p = parentMap.get(p);
        }
        while (!ancestors.contains(q)){
         	q = parentMap.get(q);
        }
        return q;
    }
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

递归方式
如果left为null表示两个节点在root的右子树，如果right为null表示两个节点在root的左子树，否则的话是root的左右子树上

     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root== null || root == p || root == q)
            return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left == null)
            return right;
        if (right == null)
            return left;
        return root;
    }
1
2
3
4
5
6
7
8
9
10
11