236. Lowest Common Ancestor of a Binary Tree.md

236. Lowest Common Ancestor of a Binary Tree

---

Difficulty : Medium

Related Topics : Tree

---

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [1,2], p = 1, q = 2
Output: 1

Constraints:

• The number of nodes in the tree is in the range [2, 10^5].
• -10^9 <= Node.val <= 10^9
• All Node.val are unique.
• p != q
• p and q will exist in the tree.

---

Solution

• mine
  • Java
    • Runtime: 4 ms, faster than 100.00%, Memory Usage: 40.7 MB, less than 14.61% of Java online submissions

      TreeNode res = null;
      public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
          if(root == p || root == q) return root;
          dfs(root, p, q);
          return res;
      }
      
      TreeNode dfs(TreeNode node, TreeNode p, TreeNode q){
          if(res != null || node == null) return null;
          if(p == node) {
              if(dfs(node, q)){
                  res = node;
              }
              return node;
          }
      
          TreeNode l = dfs(node.left, p , q);
          if(l == null && res == null){
              l = dfs(node.right, p, q);
          }
          if(l != null && res == null){
              if(dfs(node, q)){
                  res = node;
              }
              return node;
          }
          return null;
      }
      
      boolean dfs(TreeNode node, TreeNode q){
          if(node == null) return false;
          if(node == q) return true;
          return dfs(node.left, q) || dfs(node.right, q);
      
      }
      

---

• the most votes

• Runtime: 4 ms, faster than 100.00%, Memory Usage: 41.1 MB, less than 14.61% of Java online submissions

  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);
      TreeNode right = lowestCommonAncestor(root.right, p, q);
      return left == null ? right : right == null ? left : root;
  }
  

---