二元樹兩個節點的最近公共祖先問題

作者：Grey

原文地址：

部落格園：二元樹兩個節點的最近公共祖先問題

CSDN：二元樹兩個節點的最近公共祖先問題

題目描述

給定一棵二元樹的頭節點 head，和另外兩個節點 a 和 b , 返回 a 和 b 的最低公共祖先。

題目連結見：LeetCode 236. Lowest Common Ancestor of a Binary Tree

主要思路：

本題也是利用二元樹的遞迴套路來解。

定義好 Info 資訊

    public static class Info {
        public Info(boolean findA, boolean findB, TreeNode ancestor) {
            this.findA = findA;
            this.findB = findB;
            this.ancestor = ancestor;
        }
        private boolean findA;
        private boolean findB;
        private TreeNode ancestor;

    }

其中

findA表示能否在當前(子)樹下找到 a 節點；

findB表示能否在當前(子)樹下找到 b 節點；

ancestor表示當前兩個節點的最低公共祖先是什麼。

首先考慮一些邊界條件，例如

if (a == null) {
    // a 為 null，不管 b 是否為 null，公共祖先都是 b
    return b;
}
if (b == null) {
    // b 為 null， 不管 a 是否為 null，公共祖先都是 a
    return a;
}

定義遞迴函數

Info p(TreeNode head, TreeNode a, TreeNode b)

遞迴含義是：以 head 為頭的樹，a 和 b 的公共祖先是什麼，封裝成 Info 返回。

接下來看遞迴函數的主要邏輯

首先是 base case，如果 head 為 null，則 findA = false，findB = false，a 和 b 的公共祖先也是 null

即

        if (head == null) {
            return new Info(false, false, null);
        }

分析了 base case，接下來是普遍情況，如果 head 不為 null，則去左樹收集資訊，去右樹也收集資訊，然後把左右兩樹的資訊整合成 head 的資訊返回

即

// 左樹收集資訊
Info leftInfo = p(head.left, a, b);
// 右樹收集資訊
Info rightInfo = p(head.right, a, b);

// 整合
......

最後，我們需要把左右兩樹返回的資訊進行整合，首先，以 head 為頭的樹，findA的取值取決於如下三種情況：

情況1，左樹包含 a，即 leftInfo.findA

情況2，右樹包含 a，即 rightInfo.findA

情況3，head 就是 a

三個情況有一個滿足，以 head 為頭的樹 findA = true，

findB類似，

即下述程式碼所表達的含義

//  這
boolean findA = leftInfo.findA || rightInfo.findA || head == a;
boolean findB = leftInfo.findB || rightInfo.findB || head == b;

接下來看兩個節點的最低公共祖先，首先，如果左樹上找到 a 和 b，那麼 leftInfo.ancestor 就是 a 和 b 的最低公共祖先；

如果右樹上找到 a 和 b，那麼 rightInfo.ancestor 就是 a 和 b 的最低公共祖先；

如果左右樹一邊找到一個，則 head 就是 a 和 b 的最低公共祖先；

如果 a 和 b 在樹上都找不到，即findA = false, findB = false，那麼 a 和 b 的最低公共祖先就是 null。

即下述程式碼邏輯

        
        if (findA && findB) {
            if (leftInfo.findA && leftInfo.findB) {
                return new Info(true, true, leftInfo.ancestor);
            } else if (rightInfo.findA && rightInfo.findB) {
                return new Info(true, true, rightInfo.ancestor);
            }
            return new Info(true, true, head);
        }
        return new Info(findA, findB, null);

完整程式碼見

class Solution {
    public static TreeNode lowestCommonAncestor(TreeNode head, TreeNode a, TreeNode b) {
        if (a == null) {
            return b;
        }
        if (b == null) {
            return a;
        }
        // o1和o2都不為null
        return p(head, a, b).ancestor;
    }

    public static Info p(TreeNode head, TreeNode a, TreeNode b) {
        if (head == null) {
            return new Info(false, false, null);
        }
        Info leftInfo = p(head.left, a, b);
        Info rightInfo = p(head.right, a, b);
        boolean findA = leftInfo.findA || rightInfo.findA || head == a;
        boolean findB = leftInfo.findB || rightInfo.findB || head == b;
        if (findA && findB) {
            if (leftInfo.findA && leftInfo.findB) {
                return new Info(true, true, leftInfo.ancestor);
            } else if (rightInfo.findA && rightInfo.findB) {
                return new Info(true, true, rightInfo.ancestor);
            }
            return new Info(true, true, head);
        }
        return new Info(findA, findB, null);
    }

    public static class Info {
        public Info(boolean findA, boolean findB, TreeNode ancestor) {
            this.findA = findA;
            this.findB = findB;
            this.ancestor = ancestor;
        }

        private boolean findA;
        private boolean findB;
        private TreeNode ancestor;

    }
}

時間複雜度為O(N)（即一次後序遍歷的時間複雜度）

演演算法和資料結構筆記

二元樹兩個節點的最近公共祖先問題

二元樹兩個節點的最近公共祖先問題

題目描述

更多