Lowest Common Ancestor

Lowest Common Ancestor.png

解題思路 :

LCA 的第一題 沒有 parent pointer 所以回 true 的條件為
1.root = A or root = B
2.root 左邊跟 root 右邊都檢查出有 A 或著 B 存在 (即 A, B 在 root 兩邊)

C++ code :

<pre><code>
class Solution {

public:

/**
 * @param root: The root of the binary search tree.
 * @param A and B: two nodes in a Binary.
 * @return: Return the least common ancestor(LCA) of the two nodes.
 */

TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *A, TreeNode *B) {
    // write your code here
    if(!root || root == A || root == B) return root;
    TreeNode *left = lowestCommonAncestor(root->left, A, B);
    TreeNode *right = lowestCommonAncestor(root->right, A, B);
    if(left && right) return root;
    return left? left : right;
}

};

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容