二叉树的最近公共祖先2

---

题目：

题解：

1、前序遍历

• 解题思路：

  

• 复杂度分析：

  • 时间复杂度 O(N) ： 其中 NN 为二叉树节点数；最差情况下，需要递归遍历树的所有节点。
  • 空间复杂度 O(N) ： 最差情况下，递归深度达到 NN ，系统使用 O(N)O(N) 大小的额外空间。

• 代码：

  class Solution {
      public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  
          if (root == null || p == root || q == root) {
              return root;
          }
  
          TreeNode left = lowestCommonAncestor(root.left,p,q);
          TreeNode right = lowestCommonAncestor(root.right,p,q);
  
          // 当left和right同时为空，说明root的左右子树中都不包含p,q,返回null;（可省略）
          // if (left == null && right == null) return null;
  
          // 当 left 为空 ，right 不为空 ：p,q 都不在 root 的左子树中，直接返回 right 。
          // 1. p,q 其中一个在 root 的 右子树 中，此时 right 指向 p（假设为 p ）；
          // 2. p,q 两节点都在 root 的 右子树 中，此时的 right 指向 最近公共祖先节点 ；
          if (left == null) return right;
          // 同理
          if (right == null) return left;
  
          // 当 left 和 right 同时不为空 ：说明 p, q 分列在 root 的 异侧 （分别在 左 / 右子树），
          // 因此 root 为最近公共祖先，返回 root ；
          return root;
      }
  }