Reference:
http://blog.csdn.net/v_july_v/article/details/18312089
(1) Is the tree a BST or not?
BST的话,我们就能按照BST的定义思考了。当前遍历的node如果比我们要找的两个点都大,说明那两个点都在当前node的左边,所以这两个node的祖先肯定在当前node的左边,所以往左边找。反之,往右边找。如果这两个点一个大于当前node一个小于当前node,说明当前node就是LCA。 如果这两个点一个是另一个的祖先,那么这个点就是LCA。
代码如下:
1 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
2 if(p.val < root.val && q.val < root.val)
3 return lowestCommonAncestor(root.left, p, q);
4 else if(p.val > root.val && q.val > root.val)
5 return lowestCommonAncestor(root.right, p, q);
6 else
7 return root;
(2)那如果不是BST呢?一般Binary Tree.
a. Tree结构中没有parent域。
递归找。
代码如下:
b. 如果有parent域。
转化为两个linkedlist的交点问题。
代码如下:
Original: https://www.cnblogs.com/springfor/p/4141924.html
Author: 爱做饭的小莹子
Title: Lowest Common Ancestor of Two Nodes in a Binary Tree
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/540089/
转载文章受原作者版权保护。转载请注明原作者出处!