Try   HackMD

236. Lowest Common Ancestor of a Binary Tree


My Solution

The Key Idea for Solving This Coding Question

C++ Code

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) { if (root == nullptr) { return nullptr; } if (root == p || root == q) { return root; } TreeNode *leftSubtree = lowestCommonAncestor(root->left, p, q); TreeNode *rightSubtree = lowestCommonAncestor(root->right, p, q); if (leftSubtree == nullptr) { // Both p and q are not located in the left subtree. // Because p and q exist in the binary tree, they are in the // right subtree. return rightSubtree; } if (rightSubtree == nullptr) { // Both p and q are not located in the right subtree. // Because p and q exist in the binary tree, they are in the // left subtree. return leftSubtree; } // Both leftSubtree and rightSubtree are not nullptr. // root is the lowest common ancestor of p and q. return root; } };

Time Complexity

O(n)

  • n
    is the number of nodes in the binary tree.

Space Complexity

O(H)

  • H
    is the height of the binary tree.
  • For the best case, the height of the tree is
    logn
    , which is a balanced binary tree. The best space complexity is
    O(logn)
    .
  • For the worst case, the height of the tree is
    n
    , which is a skewed binary tree. The worst complexity is
    O(n)
    .

Miscellane