【经典算法题】二叉树的进阶

朴灿烈づ我的快乐病毒、 2024-05-25 17:33 81阅读 0赞

## **前言：** ##

**二叉树的算法题的总纲离不开递归，而其较难的题目往往递归较为复杂让人难以想到，本文带来几道经典的二叉树题目。**

--------------------

**目录**

前言：

一：最低公共祖先

1:题目

2：题目分析

3：代码

二：二叉树的最大路径和

1：题目

2：题目分析

3：代码

三：最大二叉搜索子树的大小

1:题目

2：题目分析

3：代码

--------------------

## 一：最低公共祖先 ##

### 1:题目 ###

> 力扣链接：[二叉树的最近公共祖先][Link 1]
> 
> 题目描述：
> 
> 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
> 
> 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
> 
> ![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5LmQ55qE5pif55CD_size_20_color_FFFFFF_t_70_g_se_x_16][]

### 2：题目分析 ###

> ?：我们分析任意一颗子树是否找到最低公共祖先，记：以x为头的子树是否找到最低公共祖先，会有以下四种情况。
> 
> **1）最低公共祖先已经找到在x的左子树上。**
> 
>  **2）最低公共祖先已经找到在x的右子树上。**
> 
>  **3）最低公共祖先已经找到汇聚在x节点处。**
> 
>  **4)以x为头的这颗子树未找到最低公共祖先。**
> 
> **我们分析可以得出，情况一和情况二都可以直接由左右子树收集的信息得到，即通过递归向左右子树要是否找到最低公共祖先的信息。而情况四只需返回null。**
> 
> **现在我们来分析情况三，最低公共祖先想要汇聚在x节点处，必须满足p和q节点都在以x为头的这颗子树上，具体情况只有以下两种可能：**
> 
> **1）p和q均找到了，一个在x的左子树上，一个在x的右子树上，此时，最低公共祖先必然是x节点。**
> 
>  **2）x节点是p节点或者是q节点，而另外一个节点在x的左子树或者右子树上。此时，最低公共祖先也是x节点。**
> 
> **?:其实通过细心分析可以发现，上面两种情况可以统一为一种情况，如果最低公共祖先没有在左右子树上找到，而在x为头的整颗子树上又找到了p节点和q节点，此时最低公共祖先必然是x节点。**

###  ###

### 3：代码 ###

public class Info{
            public boolean findP;
            public boolean findQ;
            public TreeNode ancestor;
            public Info(boolean findP,boolean findQ,TreeNode ancestor){
                this.findQ=findQ;
                this.findP=findP;
                this.ancestor=ancestor;
            }
        }
        public Info process(TreeNode node,TreeNode p,TreeNode q){
            //base case
            if(node==null){
                return new Info(false,false,null);
            }
            Info leftInfo=process(node.left,p,q);
            Info rightInfo=process(node.right,p,q);
            //情况一和二：最低公共祖先在左子树或者右子树上
            if(leftInfo.ancestor!=null){
                return new Info(true,true,leftInfo.ancestor);
            }
            if(rightInfo.ancestor!=null){
                return new Info(true,true,rightInfo.ancestor);
            }
            //情况三：最低公共祖先在x节点
            boolean findP=(node==p||leftInfo.findP||rightInfo.findP);
            boolean findQ=(node==q||leftInfo.findQ||rightInfo.findQ);
            if(findP&&findQ){
                return new Info(true,true,node);
            }
            //情况四：最低公共祖先没找到
            return new Info(findP,findQ,null);
        }
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            return process(root,p,q).ancestor;
        }

--------------------

## 二：二叉树的最大路径和 ##

### 1：题目 ###

> 题目：路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
> 
> 路径和 是路径中各节点值的总和。
> 
> 给你一个二叉树的根节点 root ，返回其 最大路径和 。
> 
> **力扣链接：[二叉树的最大路径和][Link 2]**

### 2：题目分析 ###

> ?：经过分析可以得出任意一颗子树的最大路径和，记作以x为头的整棵树,有以下六种情况：
> 
>  **1）最大路径和在x的左子树上**
> 
>  **2) 最大路径和在x的右子树上**
> 
>  **3)最大路径和是x节点的权值**
> 
>  **4）最大路径和是头节点加上左子树从头开始的最大路径和**
> 
>  **5) 最大路径和是头节点加上右子树从头开始的最大路径和**
> 
>  **6)最大路径和是头节点加上左子树从头开始的最大路径和加上右子树从头开始的最大路径和。**
> 
> 由于我们求的是最大值，而最大值只有上面六种情况，所以整颗二叉树的最大路径和必然是以上六种情况的最大值。

### 3：代码 ###

public class Info{
            public int maxDistance;
            public int maxDistanceFromHead;
            public Info(int a,int b){
                maxDistance=a;
                maxDistanceFromHead=b;
            }
        }
        public Info process(TreeNode node){
            if(node==null){
                return new Info(-2000,-2000);
            }
            Info leftInfo=process(node.left);
            Info rightInfo=process(node.right);
            //情况一:
            int p1=leftInfo.maxDistance;
            //情况二：
            int p2=rightInfo.maxDistance;
            //情况三：
            int p3=node.val;
            //情况四：
            int p4=node.val+leftInfo.maxDistanceFromHead;
            //情况五:
            int p5=node.val+rightInfo.maxDistanceFromHead;
            //情况六:
            int p6=node.val+leftInfo.maxDistanceFromHead+
            rightInfo.maxDistanceFromHead;
            int maxDistanceFromHead=Math.max(Math.max(p3,p4),p5);
            int maxDistance=Math.max(Math.max(p1,p2),Math.max(maxDistanceFromHead,p6));
            return new Info(maxDistance,maxDistanceFromHead);
        }
        public int maxPathSum(TreeNode root) {
            return process(root).maxDistance;
        }

--------------------

## 三：最大二叉搜索子树的大小 ##

### **1:题目** ###

> **?：题目 二叉树可能整体不是二叉搜索树，但可能某个子树是二叉搜索树，请返回一个二叉树的最大二叉搜索子树的大小。**

### 2：题目分析 ###

> ?：我们分析任意一颗子树的最大二叉搜索子树，记为以x为头的整颗树，整棵树的最大二叉搜索子树有如下三种可能：
> 
>  **1）最大二叉搜索子树在x的左子树上。**
> 
>  **2）最大二叉搜索子树在x的右子树上。**
> 
>  **3）最大二叉搜索子树是x为头的这棵树**
> 
> 情况一和情况二都可以通过递归向左右子树收集到信息，这两种情况是一定存在的，而情况三只有当x为头的这整棵树是二叉搜索子树时才存在，这种情况是可能存在的。

### 3：代码 ###

//给你一个头节点head，请返回最大二叉搜索子树的大小
        //大小为节点个数
    
        //分析得到答案的可能性
        //(1)与x无关，该情况一定会存在
        //左子树上的最大二叉搜索子树的大小和右子树上的最大二叉搜索子树的大小的较大者
        //(2)与x有关，x是最大二叉搜索子树的头节点
        //这种情况需满足x为头的树是二叉搜索树的情况下成立
        //此时左子树的最大二叉搜索子树就是左子树
        //右子树的最大二叉搜索子树就是右子树
        //此情况下为左数二叉搜索子树，与右子树最大二叉搜索子树的和+1
    
        public static class TreeNode{
            public int value;
            public TreeNode left;
            public TreeNode right;
            public TreeNode(int val){
                value=val;
            }
        }
        public static class Info{
            public int maxBSTSize;
            public boolean isBST;
            public int max;
            public int min;
            public Info(int a,boolean b,int c,int d){
                maxBSTSize=a;
                isBST=b;
                max=c;
                min=d;
            }
        }
        public static int maxBSTSize(TreeNode root){
            if(root==null){
                return 0;
            }
            return process(root).maxBSTSize;
        }
        public static Info process(TreeNode node){
            if(node==null){
                return null;
            }
            Info leftInfo=process(node.left);
            Info rightInfo=process(node.right);
            int max=node.value;
            int min=node.value;
            if(leftInfo!=null){
                max=Math.max(max, leftInfo.max);
                min=Math.min(min, leftInfo.min);
            }
            if(rightInfo!=null){
                max=Math.max(max, rightInfo.max);
                min=Math.min(min, rightInfo.min);
            }
            boolean isBST=false;
            if((leftInfo==null?true: leftInfo.isBST)&&(
                    rightInfo==null?true: rightInfo.isBST
                    )&&(leftInfo==null?true:leftInfo.max<node.value)&&
                    (rightInfo==null?true:rightInfo.min>node.value)){
                isBST=true;
            }
            int p1=Math.max(leftInfo==null?Integer.MIN_VALUE:leftInfo.maxBSTSize,
                    rightInfo==null?Integer.MIN_VALUE:rightInfo.maxBSTSize);
            int p2=0;
            if(isBST){
                p2=(leftInfo==null?0: leftInfo.maxBSTSize)+(rightInfo==null?0: rightInfo.maxBSTSize)
                        +1;
            }
            int maxBSTSize=Math.max(p1,p2);
            return new Info(maxBSTSize,isBST,max,min);
        }

--------------------

**由于本人水平十分有限，若有错误请即使告知！如果有帮助别忘了**

**点赞? 收藏✨ 关注✌**

[Link 1]: https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5LmQ55qE5pif55CD_size_20_color_FFFFFF_t_70_g_se_x_16]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/25/4686ed11edf94806ae934fd67504808d.png
[Link 2]: https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/