236. Lowest Common Ancestor of a Binary Tree

本文主要是介绍236. Lowest Common Ancestor of a Binary Tree，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

When we get this problem, we need to confirm the following 2 questions:

1. Can root, p or q be null? (No)

2. Can p be equal to q? (No)

We look "root" as a pointer, the point will check recursively of it's left and right sub-tree.

If the left return null, the p and q must be in right sub-tree, and if the right return null, the p and q must be in left sub-tree.

But if both left and right are not null, the p and q must be one in left and one in right, the current point should be the result.

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root ==null)
            return null;
        if(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;
        else if(right==null)
            return left;
        else
            return root;

    }

这篇关于236. Lowest Common Ancestor of a Binary Tree的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！