本文共 632 字,大约阅读时间需要 2 分钟。
找出BST中的两节点的最低公共祖先
充分利用BST特性,如果p、q均在同一子树上,那么p、q的val与root的val的关系相同,或者root的val等于p或q
递归非递归的区别在于注意处理比较p、q、root的时候,分别是大于零和小于一
public class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { while ((root.val - p.val) * (root.val - q.val) > 0) { root = root.val > p.val ? root.left : root.right; } return root; }}
public class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { return ((root.val - p.val) * (root.val - q.val) < 1) ? root : lowestCommonAncestor(root.val > p.val ? root.left : root.right, p, q); }}
转载地址:http://qahld.baihongyu.com/