LeetCode75-236-LCA-BT

🧠 Summary of Thoughts

We find p and q traverse from bottom to top, but it’s generally believe that we can only traverse from top to bottom. But how can we traverse from bottom to top? Although we cannot traverse from bottom to top, we still can deal the order with binary tree from bottom to top. So we can think about backtrack. Remember that the order(postorder traversal) for backtrack is left -> right -> root.

• if root == null, then return null.
• if left node returns not NULL, then it may consist p or q. else if right node returns not NULL, then it may consist p or q. So left treeNode and right treeNode have p and q, so the current root treeNode is lowest common ancestor.
• Then I used postorder traversal, first traverse left treeNode, and then traverse right treeNode, to get left and right recursive’s results. After that, I considered the logic of root (medium):
  • if (left != null && right != null), so the current root is LCA. Then continuously return the current root to the top.
  
  • if (left == null && right != null), return right. (if left doesn’t find p or q, however, right exists p or q, then continuously return right result)
  
  • if (left != null && right == null), return left.
  • if (left == null && right == null), return null.

✅ Code（Java）

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) {
            return root;
        } else if (left == null && right != null) {
            return right;
        } else if (left != null && right == null) {
            return left;
        } else {
            return null;
        }
    }
}