首页 > 代码库 > LeetCode 235 Lowest Common Ancestor of a Binary Search Tree
LeetCode 235 Lowest Common Ancestor of a Binary Search Tree
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”
_______6______ / ___2__ ___8__ / \ / 0 _4 7 9 / 3 5
For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
思路：
利用二叉树的性质，根节点的值小于左子树的值而小于右子树的值，因此可以根据这一性质，递归判断p,q结点在哪一棵子树中。
解法：
1 /* 2 public class TreeNode 3 { 4 int val; 5 TreeNode left; 6 TreeNode right; 7 8 TreeNode(int x) 9 { val = x; }10 }11 */12 13 public class Solution14 {15 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)16 {17 if(root == null || p == null || q == null)18 return null;19 20 if(p.val < root.val && q.val < root.val)21 return lowestCommonAncestor(root.left, p, q);22 else if(p.val > root.val && q.val > root.val)23 return lowestCommonAncestor(root.right, p, q);24 else25 return root;26 }27 }
LeetCode 235 Lowest Common Ancestor of a Binary Search Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。