fueanta

LeetCode 236: Lowest Common Ancestor of a Binary Tree

Jun 30th, 2021 (edited)
1,452
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // **Constraints:
  2.  
  3. // * The number of nodes in the tree is in the range [2, 105].
  4. // * -109 <= Node.val <= 109
  5. // * All Node.val are unique.
  6. // * p != q
  7. // * p and q will exist in the tree.
  8.  
  9.  
  10. /**
  11.  * Definition for a binary tree node.
  12.  * class TreeNode {
  13.  *     val: number
  14.  *     left: TreeNode | null
  15.  *     right: TreeNode | null
  16.  *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
  17.  *         this.val = (val===undefined ? 0 : val)
  18.  *         this.left = (left===undefined ? null : left)
  19.  *         this.right = (right===undefined ? null : right)
  20.  *     }
  21.  * }
  22.  */
  23.  
  24. function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
  25.     if (root === null)
  26.         return null;
  27.    
  28.     if (root.val === p.val || root.val === q.val)
  29.         return root;
  30.    
  31.     const lcaInLeft = lowestCommonAncestor(root.left, p, q);
  32.     const lcaInRight = lowestCommonAncestor(root.right, p, q);
  33.    
  34.     if (lcaInLeft && lcaInRight)
  35.         return root;
  36.    
  37.     return lcaInLeft ? lcaInLeft : lcaInRight;
  38. }
RAW Paste Data