二叉树的最近公共祖先

题目描述

🔗
image.png

解题思路

  • 确定递归函数返回值以及参数

需要递归函数返回值，来告诉我们是否找到节点q或者p，那么返回值为bool类型就可以了。
但我们还要返回最近公共节点，可以利用上题目中返回值是TreeNode * ，那么如果遇到p或者q，就把q或者p返回，返回值不为空，就说明找到了q或者p。

  • 确定终止条件

如果找到了 节点p或者q，或者遇到空节点，就返回。

  • 确定单层递归逻辑

值得注意的是 本题函数有返回值，是因为回溯的过程需要递归函数的返回值做判断，但本题我们依然要遍历树的所有节点。如果left 和 right都不为空，说明此时root就是最近公共节点。这个比较好理解
如果left为空，right不为空，就返回right，说明目标节点是通过right返回的，反之依然。

image.png 

  1. // 递归法
  2. public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  3.     // 找到了直接返回
  4.     if (root == p || root == q || root == null) {
  5.         return root;
  6.     }
  8.     TreeNode left = lowestCommonAncestor(root.left, p, q);
  9.     TreeNode right = lowestCommonAncestor(root.right, p, q);
  11.     if (left == null && right != null) return right;
  12.     else if (left != null && right == null) return left;
  13.     else if (left != null && right != null) return root;
  14.     return null;
  15. }

注意这种特殊情况
image.png
在root == 5的好时候已经不在递归，最后还是返回的是5.