235. 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
最近公共祖先 - 图1

示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2和节点 8的最近公共祖先是 6。
示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

  • 所有节点的值都是唯一的。
  • p、q 为不同节点且均存在于给定的二叉搜索树中。

思路：可根据二叉搜索树的性质决定搜索右子树还是左子树！

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  11. class Solution {
  12.     TreeNode res = null;
  13.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  14.         if (p.val > q.val)
  15.             lowestCommonAncestor(root, q, p);
  16.         dfs(root, p, q);
  17.         return res;
  18.     }
  19.     void dfs(TreeNode root, TreeNode p, TreeNode q) {
  20.         if (root == null)
  21.             return;
  22.         if (q.val < root.val)
  23.             dfs(root.left, p, q);
  24.         else if (p.val > root.val)
  25.             dfs(root.right, p, q);
  26.         else
  27.             res = root;
  28.     }
  29. }

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：
最近公共祖先 - 图2
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5和节点 1的最近公共祖先是节点 3 。
示例 2：
最近公共祖先 - 图3
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5和节点 4的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1


提示：

  • 树中节点数目在范围 [2, 10] 内。
  • -10 <= Node.val <= 10
  • 所有 Node.val 互不相同 。
  • p != q
  • p 和 q 均存在于给定的二叉树中。

思路：
比二叉搜索树稍微难一点，根据当前节点无法判断p和q的位置，使用后序遍历！

  1. 如果p和q分别位于当前节点的左右子树且目标节点为null，目标节点为本节点
  2. 如果p为当前节点且q位于当前节点的左子树或右子树且目标节点为null，目标节点为本节点
  3. 如果q为当前节点且p位于当前节点的左子树或右子树且目标节点为null，目标节点为本节点
  1. class Solution {
  2.     TreeNode res = null;
  3.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  4.         dfs(root, p, q);
  5.         return res;
  6.     }
  7.     boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
  8.         if (root == null)
  9.             return false;
  10.         boolean cur = false;
  11.         if (root.val == p.val || root.val == q.val)
  12.             cur = true;
  14.         boolean isLeft = dfs(root.left, p, q);
  15.         boolean isRight = dfs(root.right, p, q);
  16.         if (isLeft && isRight && res == null) {
  17.             res = root;
  18.             return true;
  19.         }
  20.         if (cur && (isRight || isLeft) && res == null) {
  21.             res = root;
  22.             return true;
  23.         }
  24.         return cur || isLeft || isRight;
  25.     }
  26. }