二叉树两个节点的最近公共祖先问题

二叉树两个节点的最近公共祖先问题

作者：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)（即一次后序遍历的时间复杂度）

更多

算法和数据结构笔记