剑指offer-81、⼆叉搜索树的最近公共祖先 _

题⽬描述给定⼀个⼆叉搜索树, 找到该树中两个指定节点的最近公共祖先。对于该题的最近的公共祖先定义:对于有根树T的两个结点p 、q 最近公共祖先LCA(T,p,q)表示⼀个结点x 满⾜x 是p 和q 的祖先且x 的深度尽可能⼤。在这⾥⼀个节点也可以是它⾃⼰的祖先.⼆叉搜索树是若它的左⼦树不空则左⼦树上所有结点的值均⼩于它的根结点的值 若它的右⼦树不空则右⼦树上所有结点的值均⼤于它的根结点的值所有节点的值都是唯⼀的。p 、q 为不同节点且均存在于给定的⼆叉搜索树中。如果给定以下搜索⼆叉树: {7,1,12,0,4,11,14,#,#,3,5} 如下图:示例1输⼊: {7,1,12,0,4,11,14,#,#,3,5},1,12输出: 7说明节点1 和 节点12的最近公共祖先是7示例2输⼊: {7,1,12,0,4,11,14,#,#,3,5},12,11输出: 12说明因为⼀个节点也可以是它⾃⼰的祖先.所以输出12思路及解答迭代遍历二叉搜索树BST的特性通过迭代查找公共祖先根据节点值大小关系决定向左子树或右子树查找javapublic class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root null) return null; TreeNode current root; while (current ! null) { // 如果p和q的值都小于当前节点LCA在左子树 if (p.val current.val q.val current.val) { current current.left; } // 如果p和q的值都大于当前节点LCA在右子树 else if (p.val current.val q.val current.val) { current current.right; } // 否则当前节点就是LCA else { return current; } } return null; // 未找到 } }时间复杂度O(h)h为树高平均O(log n)最坏O(n)空间复杂度O(1)只使用常数空间递归遍历递归判断节点值关系决定向左或右递归查找题⽬已经保证了两个节点 p , q 都在树上我们取出根节点 7 假设⼩于 7 则在左⼦树如果⼤于7 则在右⼦树。需要查找的两个节点但凡有⼀个等于根节点它们的⽗节点就是根节点因为⼀个节点的⽗节点可以是⾃身题⽬有说明。如果⼀个⼤于根节点⼀个⼩于更节点其最近公共祖先也是根节点。如果两个都⼤于或者两个都⼩于怎么办当然是递归如果两个都⼩于那么就取当前的左⼦树进⾏递归直到符合要求。⽐如查找3 和 5由于 3 和 5 都⼩于 7那么取左⼦树 1 下⾯的进⾏递归javaclass TreeNode { int val 0; TreeNode left null; TreeNode right null; public TreeNode(int val) { this.val val; } } public class Solution68 { public int lowestCommonAncestor(TreeNode root, int p, int q) { TreeNode result commonAncestor(root, p, q); return result null ? -1 : result.val; } public TreeNode commonAncestor(TreeNode root, int p, int q) { // 等于空 if (root null) { return null; } if (root.val p || root.val q) { // 有⼀个值等于根节点 return root; } // 在左⼦树 if (p root.val q root.val) { return commonAncestor(root.left, p, q); } else if (p root.val q root.val) { // 两个都在右⼦树 return commonAncestor(root.right, p, q); } else { return root; } } }时间复杂度O(h)递归深度为树高空间复杂度O(h)递归调用栈空间通用二叉树假设这道题条件改⼀下如果不是⼆叉搜索树怎么办如果不是⼆叉搜索树那么我们不能直接判断出它在左⼦树还是在右⼦树。不如暴⼒点先在左⼦树中找如果右⼦树没找到说明都在左⼦树如果左⼦树没找到说明都在右⼦树如果两个都分别存在说明当前节点就是他们的⽗节点。javapublic class Solution68 { public int lowestCommonAncestor(TreeNode root, int p, int q) { TreeNode result commonAncestor(root, p, q); return result null ? -1 : result.val; } public TreeNode commonAncestor(TreeNode root, int p, int q) { if (null root) { return null; } if (root.val p || root.val q) { return root; } TreeNode left commonAncestor(root.left, p, q); TreeNode right commonAncestor(root.right, p, q); if (left null) { return right; } else if (right null) { return left; } else { return root; }