【重温经典】二叉树的最近公共祖先

方法1：DFS

思路：

1.left和right都为空，说明root的左右子树中都不包含p和q节点，返回null即可

2.left不为空，right为空，说明p和q不在右子树中（因为右子树为空了），这时，返回left，这里面有下面的两种情况：

• p和q都在left即左子树上，而root节点恰好指向了p或者q

• p和q都在left即左子树上，而root节点未指向了p或者q，指向的是最近公共祖先节点

3.right不为空，left为空，说明p和q不在左子树中（因为左子树为空了），这时，返回right，这里面有下面的两种情况：

• p和q都在right即右子树上，而root节点恰好指向了p或者q

• p和q都在right即右子树上，而root节点未指向了p或者q，指向的是最近公共祖先节点

4.left不为空，并且right不为空，说明p和q分布在root节点的左右子树的两侧，这时root为p和q的最近公共祖先节点，返回

   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 && right !=null) return root;
        if(left !=null) return left;
        if(right!=null) return right;
        return null;
    }

测试

        public static void main(String[] args) {
            _3rd handler = new _3rd();
            TreeNode root = TreeNodeIOUtils.transform("[3,5,1,6,2,0,8,null,null,7,4]");
            TreeNode p = root.left;//5
            TreeNode q = root.right;//1
//            TreeNode ancestor = handler.lowestCommonAncestor(root, p, q);
//            System.out.printf("%d\n", ancestor.val);
            root = TreeNodeIOUtils.transform("[3,5,1,6,null,null,null,7,2,null,null,null,4]");
            p = root.left.left.left;
            q = root.left.left.right.right;
            TreeNode ancestor = handler.lowestCommonAncestor(root, p, q);
            System.out.printf("%d\n", ancestor.val);
        }

方法2：迭代

 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            //存当前节点的父节点，k:当前节点，v:当前节点的父节点，root节点的父节点为null
            Map<TreeNode, TreeNode> parent = new HashMap<>();
            parent.put(root, null);
            Deque<TreeNode> stk = new ArrayDeque<>();
            stk.push(root);
            //step1:率先找到p或者q，先左节点，后右节点，然后出栈的时候，选右节点优先
            while (!parent.containsKey(p) || !parent.containsKey(q)) {
                TreeNode cur = stk.pop();
                if (cur.left != null) {
                    parent.put(cur.left, cur);
                    stk.push(cur.left);
                }
                if (cur.right != null) {
                    parent.put(cur.right, cur);
                    stk.push(cur.right);
                }
            }
            //step2：set收集的是p节点的所有祖先节点，包括p节点的直系父节点
            Set<TreeNode> set = new HashSet<>();
            while (p != null) {
                set.add(p);
                p = parent.get(p);
            }
            //step3:找q的父节点，第一个出现在set集合中的即是LCA
            while (!set.contains(q)) {
                q = parent.get(q);
            }
            return q;
        }