Leetcode 236 二叉樹的最近公共祖先(Lowest Common Ancestor of a Binary Tree) 題解分析

語言: CN / TW / HK

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia : “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself ).”

給定一個二叉樹, 找到該樹中兩個指定節點的最近公共祖先。

百度百科 中最近公共祖先的定義為:“對於有根樹 T 的兩個節點 pq ,最近公共祖先表示為一個節點 x ,滿足 xpq 的祖先且 x 的深度儘可能大( 一個節點也可以是它自己的祖先 )。”

程式碼

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 如果當前節點就是 p 或者是 q 的時候,就直接返回了
        // 當沒找到,即 root == null 的時候也會返回 null,這是個重要的點
        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);
        // 當左邊是 null 就直接返回右子樹,但是這裡不表示右邊不是 null,所以這個順序是不影響的
        // 考慮一種情況,如果一個節點的左右子樹都是 null,那麼其實對於這個節點來說首先兩個子樹分別呼叫
        // lowestCommonAncestor會在開頭就返回 null,那麼就是上面 left 跟 right 都是 null,然後走下面的判斷的時候
        // 其實第一個 if 就返回了 null,如此遞迴返回就能達到當子樹中沒有找到 p 或者 q 的時候只返回 null
        if (left == null) {
            return right;
        } else if (right == null) {
            return left;
        } else {
            return root;
        }
//        if (right == null) {
//            return left;
//        } else if (left == null) {
//            return right;
//        } else {
//            return root;
//        }
//        return left == null ? right : right == null ? left : root;
    }