LeetCode系列题解之二叉搜索树系列题解

╰半橙微兮° 2022-11-25 13:08 152阅读 0赞

### 文章目录 ###

*  二叉搜索树
 *   *  前言
     *  两个基础的框架部分
     *  具体示例
     *   *  简单实现版：
         *   *  \[ 二叉搜索树的最近公共祖先\](https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/)
         *  深度版
         *   *  二叉树的深度
             *  判断是否平衡二叉树
             *  二叉树的直径
         *  中序遍历版
         *   *  验证二叉
             *  距离最小值
             *  恢复二叉搜索树：
         *  路径和
         *   *  题干
             *  思路
             *  代码
         *  记录
         *   *  path-sum
             *  思路
             *  代码
         *  path-sum-II
         *   *  binay-tree-maximum-path-sum
             *  思路
             *  代码

# 二叉搜索树 #

> 广告： github上新开立了一个仓库[May-Nodes][]，本篇博客也收录其中。包括但不限于之前面试遇到的相关数据库,计算机操作系统,Java基础知识，计算机网络以及LeetCode等算法题解等知识。届时也会整理学习使用的PDF文档与资源。有需要的小伙伴 可以点个关注和`star`。在持续更新中，总会遇到你想要的。

## 前言 ##

首先明白二叉搜索树系列的特殊性：二叉搜索树(Binary Search Tree 简称为BST)，对于其的特点是任意节点的值都要大等于左子树所有节点的值，且要小于等于右边子树的所有节点的值。其左右子树的特性也就奠定了其在操作过程中就是有迹可循的。

## 两个基础的框架部分 ##

首先是二叉搜索树的总的设计理念：

void BinarySearch(TreeNode root){ 
        if(root ...)
            // 进行系列的操作；
        BinarySearch(root.left);
        BinarySearch(root.right);
    }

当然这个设计理念的思想就是说，我们只管进行具体的递归操作，具体的操作我们就可以参见是先序，中序还是后续然后做具体的操作，举个栗子：对于[700-二叉搜索树的搜索][700-]，我们只管进行左右子数的循环，其余的交给root去处理：

public TreeNode searchBST(TreeNode root, int val) { 
            if(root == null) 
            return root;
            if(root.val == val) return root;
            else  if(root.val> val) return searchBST(root.left,val);
             else return searchBST(root.right,val);
        }

其上就是对二叉树只进行查询的操作，但是不涉及到任何的修改操作，只需要简单判断即可，但是对于还有一部分的二叉搜索树而言，我们需要对左右子数进行简单的处理和判断：

举个栗子：判断一棵二叉树是否是对称的[对称的二叉树][Link 1]，就需要对节点值进行判断处理（以下的思想也是在很多地方都能够用到的思想）

1.  对于这类的题目来说，可以将逻辑块分成一个具体的函数，因为有的时候，我们的逻辑块可能并没有具体的返回值，也有的时候，想要的最后的返回值喝逻辑块在运行中的返回值不同。
2.  对于这类的题目，一般都是判断是否相等，判断两颗树是否是相等的等，都是需要对树中的值进行对应的判断处理。

public boolean isSymmetric(TreeNode pRoot) { 
           if(pRoot==null)
              
                return true;
            return issys(pRoot.left,pRoot.right);  
        }
        private boolean issys(TreeNode l,TreeNode r){ 
            if(l==null && r==null){ 
                return true;
                // 主要是判断对于两颗树来说对应的节点是否都不存在，都不存在时候 表示不用比较，就可以返回正常值。
            }
            if(l==null ||r==null){ 
                return false;
                // 表示本该对应的节点上，一个是null 一个却不是null 时候，返回一个错误的值。
            }
            if(l.val!=r.val)
            {   
                return false;
                // 注意 这里该判断两者不相等 返回一个错误值，而不是两者相等返回正确值
                // 因为 若是出现左右子数相同时候 当前是正确的 但是若是我们直接返回正确值 
                // 下面的情况 就有可能没办法得到正确的判断。
            }
            return issys(l.left,r.right)&& issys(l.right,r.left);
        }

## 具体示例 ##

### 简单实现版： ###

以上就是具体的框架部分，一个适用于对值具体查找的判断，一个使用于节点的等值判断。

#### [ 二叉搜索树的最近公共祖先][Link 2] ####

具体的题目可以去查看原题部分，这里我们进行分析，首先对于这个题目来说，只是他一棵树，然后所有的操作也都是在自身进行判断，所以我们就可以排除第二种的`判断节点是否存在问题`，就是使用到第一种的对各自节点进行判断：**判断左右方向**：我们要深析二叉搜索树的特点，让我们查找的是最近的根节点，就是说要么就是两者为左右节点，根节点不再两者之间，要么就是两者之间有一个就是共同的根节点。下面思考如何进入到左子树：就是给定的两个节点的值都比根节点要小，表示在左边，同理，给定的值都比当前的根要大，岂不就是说，当前的根节点太小了？ 如此我们就找到了判断进入左右的方法，其余的就交给**root**就好。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 
    
            if(root.val< p.val && root.val <q.val)
            return   lowestCommonAncestor(root.right,p,q);
            else if(root.val > p.val && root.val > q.val)
             return   lowestCommonAncestor(root.left,p,q);
             return root;
        }

### 深度版 ###

对于二叉树系列的深度版本而言，主要思想还是基础的进入到左右子树的循环，但是不同的是，之前我们进入到左右子树循环中，只是图一个遍历的值，现在我们需要在进行在进行遍历时候获取到一个深度值。

对于这部分的模板是我们在获取左右值的同时对左右节点的最大值进行一个计算与保存：

public int temp(TreeNode root){ 
            if(root == null)
            return 0 ;// 表示在不满足的情况下的退出
            int left =temp(root.left);
            int right = temp(root.right);
            return 1+ Math.max(left,right);// 获取到左右方最大值。
        }

#### 二叉树的深度 ####

[获取到最大深度][Link 3]

如题目所示，在进行最基础遍历的同时对左右节点进行取最大值（表示取左右节点最大值）。

public int maxDepth(TreeNode root) {   
            return temp(root);
        }
        public int temp(TreeNode root){ 
            if(root == null)
            return 0 ;
            int left =temp(root.left);
            int right = temp(root.right);
            return 1+ Math.max(left,right);
        }

#### 判断是否平衡二叉树 ####

[判断是否是平衡二叉树][Link 4]

这个题目原型就是我们的二叉树的深度的变形处理，还是要进行左右节点的深度的计算，大体的模板是相同的，为题目进行简单的变形即可。

class Solution { 
            boolean  temp = false;
        public boolean isBalanced(TreeNode root) { 
            isbalance(root);
            return !temp;
        }
        public int isbalance(TreeNode root){ 
            if(root == null)
            return 0;
             int left = isba(root.left);
            int right = isba(root.right);
            if(Math.max(left,right)-Math.min(left,right)>1){ 
                temp = true;
                // 这里我们就不能够正常的进行值返回 因为我们在计算的时候，使用到的是int类型进行深度的 计算 但是在最后进行值的判断时候 需要的是 boolean 类型 所以 这里设置一个标志位。
            }
            return 1 +Math.max(left,right);
        }
    }

#### 二叉树的直径 ####

[二叉树的直径][Link 5]

对于这个变形，主要的思维逻辑还是最开始的一套，主要是对于直径而言，需要对左右子树进行相加，表示的是所有的直径信息，然后在遍历的过程中取得较大值。

class Solution { 
         int ans;
        public int diameterOfBinaryTree(TreeNode root) { 
           ans=0;
           depth(root);
           return ans;
        }
        public int depth(TreeNode root){ 
            if(root==null)
            return 0;
            int l=depth(root.left);
            int r=depth(root.right);
            ans=Math.max(ans,l+r);
            return Math.max(l,r)+1;
        }
    }

### 中序遍历版 ###

对于寻求中序遍历系列而言，主要是利用我们最初的中序遍历的模板系列。也是我们树遍历中的三大遍历模板，对于这部分的题目主要就是利用中序的特性，对中间的代码块进行系列操作

public  void temp(TreeNode root){ 
        
        temp(root.left);
        ... // 进行系列的操作
        temp(root.right);
    }

#### 验证二叉 ####

[验证是否为二叉搜索树][Link 6]

利用中序遍历的思想进行左右的判断。

class Solution { 
        long pre=Long.MIN_VALUE;
        public boolean isValidBST(TreeNode root) { 
            if(root==null)
            return true;
            if(!isValidBST(root.left))
            return false;
            if(root.val<=pre)
            return false;
            pre=root.val;
            if(!isValidBST(root.right))
            return false;
            return true;
        }
    
    }

#### 距离最小值 ####

[二叉搜索中两两之间差最小值][Link 7]，利用到中序遍历中的`pre`指针表示当前`root`的前驱指针,两者之间进行判断即可。

class Solution { 
    TreeNode pre = null;
    int temp = Integer.MAX_VALUE;
        public int minDiffInBST(TreeNode root) { 
     minvalue(root);
     return temp;
        }
        public void  minvalue(TreeNode root){ 
            if(root== null)
            return;
            minvalue(root.left);
            if(pre!=null)
            { 
                temp =Math.min(temp,root.val-pre.val);
            }
            pre = root;
            minvalue(root.right);
        }
    }

#### 恢复二叉搜索树： ####

[恢复二叉搜索][Link 8]

基础的思想理念，需要注意的是对于这样的一个示例来说 **6 345 2**来说对于按照我们基础的交换理念 **6和3** 进行交换，但是走到后面会发现 **6和2** 也要进行交换,所以要先对前一个值（6）进行判空，判断是否还需要对其的值进行更改。

class Solution { 
        TreeNode pre,p,q;
        public void recoverTree(TreeNode root) { 
            pre = p = q = null;
            getResult(root);
            int temp = p.val;
            p.val = q.val;
            q.val = temp;
        }
        public void getResult(TreeNode root){ 
            if(root == null)
            return ;
            getResult(root.left);
            if(pre!= null &&  pre.val > root.val){ 
                if(p==null){ 
                    p = pre;
                    q = root;
                }
                else 
                q = root;
            }
            pre= root;
            getResult(root.right);
        }
    }

### 路径和 ###

#### 题干 ####

**输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)**

#### 思路 ####

1.  首先第一步而言，我们应该明白对于树的操作来言时候，遍历些许都是使用到栈与队列较多，对于树的查询，涉及到左右不定变化一般都是递归。
2.  然后对于递归而言要判断我们如何以及何时将正确的路径加入到我们的结果集中。因为题目中说到，打印的是路径，而路径又是从根节点到叶结点–即对于一个节点来说左右子树都为空的情况下就是叶子节点我们就可以对其进行一个基础的判断。
3.  输出的是 `ArrayList<ArrayList<Integer>>`类型，就需要我们对于每一个的结果集进行加入，然后对于内部的`ArrayList<Integer>`进行生成一个新的，一般对于输出结果是`ArrayList<ArrayList<Integer>>`时候我们可以这样进行操作。

ArrayList<ArrayList<Integer>> array=new ArrayList<ArrayList<Integer>>();
            ArrayList<Integer> list=new ArrayList<Integer>();
            list.add(XX);
            array.add(list);
            list=new ArrayList<Integer>();

1.  然后成功之后，例如我们已经知道了一条路径，在添加完成以后，要删除刚刚添加进来的，因为还要进行下一个结点的探索（后序在出现此类问题时候会继续深入的讲解）
2.  然后就是左右递归探索即可。

#### 代码 ####

/** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } // [[10,5,7],[10,12]] } */
    import java.util.ArrayList;
    public class Solution { 
        public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) { 
            ArrayList<ArrayList<Integer>> array=new ArrayList<ArrayList<Integer>>();
            ArrayList<Integer> list=new ArrayList<Integer>();
           if(root==null || target==0)
               return array;
           sum(root,target,array,list,0);
            return array;
        }
        private void sum(TreeNode t,int target,ArrayList<ArrayList<Integer>> array,ArrayList<Integer> list,int sum){ 
            if(t==null || target==0)
                return ;
             sum=sum+t.val;
            if( t.left==null&& t.right==null)
            { 
                if(sum==target){ 
                     list.add(t.val);
                     array.add(new ArrayList<Integer>(list)); 
                    list.remove(list.size()-1);
                }
                return;
            }
           list.add(t.val);
           sum(t.left,target,array,list,sum); 
           sum(t.right,target,array,list,sum);
            // 这个remove会在当上面的两个都遍历完成以后 顺序执行下来。
           list.remove(list.size()-1);
        }
    }

### 记录 ###

在完成剑指Offer之后，还刷到了牛客上[LeetCode经典题目][LeetCode]其中有两个题目觉得和路径问题相识，这里也放出来一起讲解一下

#### path-sum ####

**给定一个二叉树和一个值sum，判断是否有从根节点到叶子节点的节点值之和等于sum的路径，  
例如：  
给出如下的二叉树，sum=22。**

5
             4            8
         11   13     4
         7 2  5 1

#### 思路 ####

1.  对于这个题目而言同样是根节点到叶子节点，所以还是判断对于左右节点都为空时表示叶子节点，进行路径值的判断
2.  然后传参时候进行相减传参可以不用额外定义变量进行值存取，减少了工作量。
3.  因为没有进行值的存取，所以不存在上面的对remove操作。

#### 代码 ####

public class Solution { 
        public boolean hasPathSum(TreeNode root, int sum) { 
            if(root==null) return false; 
                if(root.left==null && root.right==null){ 
                    if(sum-root.val==0)
                        return true;
                    else return false;
                }
    return        hasPathSum(root.left,sum-root.val)||hasPathSum(root.right,sum-root.val);
    
        }
    }

### path-sum-II ###

就是上面的剑指Offer二十四

#### binay-tree-maximum-path-sum ####

**给定一个二叉树，请计算节点值之和最大的路径的节点值之和是多少。  
这个路径的开始节点和结束节点可以是二叉树中的任意节点  
例如：  
给出以下的二叉树，**

1
      2   3

#### 思路 ####

1.  本题的难点在于我们开始的节点是任意的节点，同时题目中隐约的表示是可能会出现有负值就有点类始于给定你一个数组，其中有正有负，让你判断连续和的最大值，就需要我们对进行相加的值进行一个与0比的操作，判断我们当前的序列值能否加入我们想得到结果的序列，就是说我们最后想得到的最大值能否包括我们此时遍历到的值。
2.  同样是递归进行操作，需要与零值进行比较，若是大于零就加入到我们想要的结果中，然后维持一个全局的变量。
3.  返回值是判断以当前节点为根的节点的左右子树和是否大于零，若是表示成功则加上当前的值，否则进行抛弃直接返回当前值，对之前就算较大值是小于零进行抛弃。

#### 代码 ####

public class Solution { 
        int max_m=Integer.MIN_VALUE;
        public int maxPathSum(TreeNode root) { 
            
            getMax(root);
            return max_m;
        }
        private int getMax(TreeNode root){ 
            if(root==null)
                return 0;
            int sum=root.val;
            int left=getMax(root.left);
            int right=getMax(root.right);
            if(left>0){ 
                sum+=left;
            }
            if(right>0){ 
                sum+=right;
            }
          max_m=Math.max(max_m,sum); 
            return Math.max(left,right)>0?root.val+Math.max(left,right): root.val;
        }
    }

[May-Nodes]: https://github.com/maycope/May-Nodes
[700-]: https://leetcode-cn.com/problems/search-in-a-binary-search-tree/
[Link 1]: https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/
[Link 2]: https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/
[Link 3]: https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/
[Link 4]: https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/
[Link 5]: https://leetcode-cn.com/problems/diameter-of-binary-tree/
[Link 6]: https://leetcode-cn.com/problems/validate-binary-search-tree/submissions/
[Link 7]: https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/
[Link 8]: https://leetcode-cn.com/problems/recover-binary-search-tree/
[LeetCode]: https://www.nowcoder.com/ta/leetcode