题目描述:Leetcode 0235 二叉搜索树的最近公共祖先
分析
-
本题的考点:LCA(最近公共祖先)。
-
关于LCA问题可以参考:网址。
-
因为是二叉搜索树,所以我们可以根据值的大小递归求解。如果两个节点的值都小于根节点的值,则进入左子树搜索;否则若两个节点的值都大于根节点的值,则进入右子树搜索;否则当前根节点就是LCA。
代码
- C++
class Solution { public: TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) { if (!root) return NULL; if (p->val < root->val && q->val < root->val) return lowestCommonAncestor(root->left, p, q); if (p->val > root->val && q->val > root->val) return lowestCommonAncestor(root->right, p, q); return root; } };
- Java
class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null) return null; if (p.val < root.val && q.val < root.val) return lowestCommonAncestor(root.left, p, q); if (p.val > root.val && q.val > root.val) return lowestCommonAncestor(root.right, p, q); return root; } }
时空复杂度分析
-
时间复杂度: O ( h ) O(h) O(h),h为树高。
-
空间复杂度: O ( h ) O(h) O(h)。
题目描述:Leetcode 0236 二叉树的最近公共祖先
分析
-
本题的考点:LCA。
-
关于LCA问题可以参考:网址。
-
后续递归遍历两棵子树,第一次发现某棵子树中既有p又有q,则该子树的根节点为p和q的最近公共祖先。如下图:
代码
- C++
// 写法一 class Solution { public: TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) { if (!root || root == p || root == q) return root; auto l = lowestCommonAncestor(root->left, p, q), r = lowestCommonAncestor(root->right, p, q); if (l && r) return root; // 第一次左右非空, 此时对应的root是LCA if (l) return l; return r; // right也可能为空节点 } };
// 写法二 class Solution { public: TreeNode* ans = NULL; TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) { dfs(root, p, q); return ans; } // 返回值是一个二进制的数,最低位是1的话表示该棵子树存在p,从右向左第二位是1的话表示该棵子树存在q。 int dfs(TreeNode *root, TreeNode *p, TreeNode *q) { if (!root) return 0; int state = 0; if (root == p) state |= 1; else if (root == q) state |= 2; state |= dfs(root->left, p, q); state |= dfs(root->right, p, q); if (state == 3 && !ans) ans = root; // 只有第一次找到的才是LCA return state; } };
- Java
class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null || root == p || root == q) return root; TreeNode left = lowestCommonAncestor(root.left, p, q), right = lowestCommonAncestor(root.right, p, q); if (left != null && right != null) return root; // 第一次左右非空, 此时对应的root是LCA if (left != null) return left; return right; // right也肯能为空节点 } }
时空复杂度分析
-
时间复杂度: O ( n ) O(n) O(n),n为树中节点数。
-
空间复杂度: O ( h ) O(h) O(h),h为树高。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)