68. 树中两个节点的最低公共祖先

68.1 二叉查找树

题目链接

Leetcode : 235. Lowest Common Ancestor of a Binary Search Tree

解题思路

在二叉查找树中,两个节点 p, q 的公共祖先 root 满足 root.val >= p.val && root.val <= q.val。

68. 树中两个节点的最低公共祖先 - 图1

  1. public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  2. if (root == null)
  3. return root;
  4. if (root.val > p.val && root.val > q.val)
  5. return lowestCommonAncestor(root.left, p, q);
  6. if (root.val < p.val && root.val < q.val)
  7. return lowestCommonAncestor(root.right, p, q);
  8. return root;
  9. }

68.2 普通二叉树

题目链接

Leetcode : 236. Lowest Common Ancestor of a Binary Tree

解题思路

在左右子树中查找是否存在 p 或者 q,如果 p 和 q 分别在两个子树中,那么就说明根节点就是最低公共祖先。

68. 树中两个节点的最低公共祖先 - 图2

  1. public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  2. if (root == null || root == p || root == q)
  3. return root;
  4. TreeNode left = lowestCommonAncestor(root.left, p, q);
  5. TreeNode right = lowestCommonAncestor(root.right, p, q);
  6. return left == null ? right : right == null ? left : root;
  7. }

68. 树中两个节点的最低公共祖先 - 图3