236. Lowest Common Ancestor of a Binary Tree

题目描述和难度

  • 题目描述:

给定一棵二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义: “对于有根树T的两个结点u、v,最近公共祖先表示一个结点x,满足x是u、v的祖先且x的深度尽可能大。”(一个节点也可以是它自己的祖先

例如,给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

示例 1:

输入: root, p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例 2:

输入: root, p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为指定节点自身。

思路分析

求解关键:这道题主要考察了二叉树的后序遍历,先分别从左右子树中递归地找出 p 和 q,如果都能找到,则说明当前结点就是要找的最近公共祖先。

参考解答

参考解答1

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 初始条件:只要等于其中之一,就返回自己,作为后序判断的依据
        // 既然是编写递归方法,首先先写出递归终止条件
        if (root == null || root == p || root == q) {
            return root;
        }
        // 先在左子树中找,p 和 q 的最近公共祖先
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        // 再在右子树中找,p 和 q 的最近公共祖先
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // 如果左边和右边两者都空,说明,p 和 q 分散在 root 的左右子树中
        if (left != null && right != null) {
            return root;
        }
        // 否则返回 left 和 right 中非空的那个
        return left == null ? right : left;
    }
}

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0236-lowest-common-ancestor-of-a-binary-tree ,如果我的题解有错误,或者您有更好的解法,欢迎您告诉我 liweiwei1419@gmail.com