This is the second time to brush this question, so you can see how frequently this question is tested. This is a swipe of the address sword pointing to the Offer — the nearest common ancestor of the binary tree (JS implementation).

Topic describes

Their thinking

  • First determine whether the current node is null, p, or Q.
    • Null: Returns NULL directly
    • P: returns p directly
    • Q: Returns q directly
  • Recursively traverses the left and right subtrees and accepts the return value
  • If the values returned by the left and right subtrees are not empty, the current parent node is the most recent common ancestor. Otherwise, the node that is not currently empty is returned as the most recent common ancestor.

AC code

var lowestCommonAncestor = function(root, p, q) {
    // Returns null if the node is empty
    if(! root )return null;

    if (root === p) return p;

    if (root === q) return q;

    let x = lowestCommonAncestor(root.left,p,q);
    let y = lowestCommonAncestor(root.right,p,q);

    if (x && y) {
        return root;
    } else {
        returnx || y; }};Copy the code

The title to reflect

  • Learn to recursively traverse a binary tree and return the target element.