《经典力扣题》二叉树基础题（一）

悠悠 2024-05-25 17:33 72阅读 0赞

## 前言： ##

**二叉树的题目绝大多数都可以利用递归来解决，熟练掌握二叉树的前中后序遍历以及层序遍历是能快速解决二叉树题目的基础。**

**目录**

前言：

二叉树的最大深度

思路：

代码：

相同的树

思路：

代码：

对称二叉树

思路：

代码：

判断平衡二叉树

思路：

代码:

利用前序遍历与中序遍历生成二叉树

分析：

代码：

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

## **二叉树的最大深度** ##

> ?:力扣链接：[二叉树的最大深度][Link 1]
> 
> **题目：输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。**

### 思路： ###

> **在审题了解到何为二叉树的最大深度后，我们可以知道一颗二叉树的最大深度，应该是左子树的最大深度和右子树的最大深度的较大者+1**
> 
> **即任意一颗子树的最大深度都等于其左子树的最大深度和右子树的最大深度+1**
> 
> 这明显是一个递归结论，我们可以通过这个递归结论写出代码。

### 代码： ###

//给定一颗二叉树返回二叉树的最大深度
        class TreeNode{
            public int val;
            public TreeNode left;
            public TreeNode right;
            public TreeNode(int val){
                this.val=val;
            }
        }
        //递归函数
        //递归含义：以node为头的这棵树的最大深度
        public int process(TreeNode node) {
            //base case
            if (node == null) {
                return 0;
            }
            return Math.max(process(node.left), process(node.right)) + 1;
        }
        public int getMaxDepth(TreeNode root){
            return process(root);
        }

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

## 相同的树 ##

> **?：力扣链接[：相同的树][Link 2]**
> 
> **题目：**
> 
> **给你两棵二叉树的根节点 `p` 和 `q` ，编写一个函数来检验这两棵树是否相同。**
> 
> **如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。**

### 思路： ###

> **分类讨论：以p和q为根的树只有以下三种种情况**
> 
> **(1):p==null&&q==null 两颗空树自然相同 return true**
> 
> **(2)(p==null)^(q==null) 两棵树有一颗为空树，另一颗非空树,一定不相同 return false**
> 
> **(3)p!=null&&q!=null**
> 
> **return p.val==q.val&&(左子树相同)&&(右子树相同)**

### 代码： ###

**通过上述思路我们可以轻易的写出代码**

public class TreeNode{
            public int val;
            public TreeNode left;
            public TreeNode right;
            public TreeNode(int val){
                this.val=val;
            }
        }
        public boolean isSame(TreeNode root1,TreeNode root2) {
            //有三种可能
            //1:root1==null&&root2==null
            //2:root1和root2有一个节点为null
            //3:root1和root2均不为空
            if(root1==null^root2==null){
                return false;
            }
    
            if(root1==null&&root2==null){
                return true;
            }
            return root1.val== root2.val&&isSame(root1.left,root2.left)&&
                    isSame(root1.right,root2.right);
        }

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

## 对称二叉树 ##

> **?：力扣链接：[对称的树][Link 3]**
> 
> **题目：给你一个二叉树的根节点 `root` ， 检查它是否轴对称。**

### 思路： ###

> 对题目进行分析我们可以得到以下的结论。
> 
> **对于任意一颗子树，如果它的左子树和右子树相同，则这颗子树是对称二叉树。**
> 
> **在这里我们就用到了上一题判断一颗二叉树是否相同的策略。通过借鉴上一题的思路，我们很快就能写出这题的代码。**

### 代码： ###

//利用判断两颗二叉树是否相等的思路一样
        //左边的左孩子等于右边的右孩子
        //左边的右孩子等于右边的左孩子
        public boolean isSymmetric(TreeNode node1,TreeNode node2){
            if((node1==null)^(node2==null)){
                return false;
            }
            if(node1==null&&node2==null){
                return true;
            }
            return node1.val==node2.val&&isSymmetric(node1.left,node2.right)&&
            isSymmetric(node1.right,node2.left);
        }
        public boolean isSymmetric(TreeNode root) {
            return isSymmetric(root,root);
        }

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

## 判断平衡二叉树 ##

> **?：力扣链接：[平衡二叉树][Link 4]**
> 
> **题目：**
> 
> **给定一个二叉树，判断它是否是高度平衡的二叉树。**
> 
> **本题中，一棵高度平衡二叉树定义为：**
> 
> **一个二叉树*每个节点* 的左右两个子树的高度差的绝对值不超过 1 。**

### 思路： ###

> **平衡二叉树的定义是任意一颗子树的左子树和右子树的高度差的绝对值不超过1**
> 
> **所以任意一颗子树是平衡二叉树的条件为**
> 
> **(1):它的左子树是平衡二叉树**
> 
> **(2):它的右子树是平衡二叉树**
> 
> **(3):它的左子树和右子树高度差不超过1**

##  ##

**通过整合上述思路我们可以快速的写出代码。**

### 代码: ###

public class Info{
            public boolean isBalanced;
            public int height;
            public Info(boolean a,int b){
                isBalanced=a;
                height=b;
            }
        }
        public Info process(TreeNode node){
            if(node==null){
                return new Info(true,0);
            }
            //向左右子树要信息
            Info leftInfo=process(node.left);
            Info rightInfo=process(node.right);
            //整合出自身的信息
            int height=Math.max(leftInfo.height,rightInfo.height)+1;
            boolean isBalanced=false;
            if(leftInfo.isBalanced&&rightInfo.isBalanced&&
            (Math.abs(leftInfo.height-rightInfo.height)<2)){
                isBalanced=true;
            }
            return new Info(isBalanced,height);
        }
        public boolean isBalanced(TreeNode root) {
            return process(root).isBalanced;
        }

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

## 利用前序遍历与中序遍历生成二叉树 ##

> **?：力扣链接：[利用前序遍历和中序遍历生成二叉树][Link 5]**
> 
> **给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。**

### 分析： ###

> **首先我们需要知道前序遍历和中序遍历的顺序。**
> 
>  **1：前序遍历：先处理头节点，再遍历左子树，再遍历右子树**
> 
>  **2：中序遍历：先遍历左子树，再处理头节点，再遍历右子树**
> 
> 这题的难点在于如何写出递归函数，这需要扎实的递归功底和coding能力。
> 
> 设计递归参数是写出递归函数的关键点，这里我们可以这样思考：
> 
> 我们现在有两个数组：一个前序数组，一个中序数组，我们可以写出这样的递归函数
> 
> 利用pre\[L1......R1\]和in\[L2.......R2\]建立出一整棵树。
> 
> (1):由于pre数组是头左右的处理顺序，所以pre\[L1\]一定是整颗树的头节点，所以我们只需要
> 
> 在pre数组中区分出左子树和右子树的范围。
> 
> 这时我们就需要考虑中序数组，因为中序数组是左头右的顺序，因此我们只需要在in\[L2...R2\]中找到pre\[L1\]的位置为find位置，在中序数组中in\[L2....find-1\]建立左子树，in\[find+1...R2\]建立右子树。
> 
> （2）：这样我们就可以利用递归去建立左子树，和右子树。

### **代码：** ###

//递归函数
        //利用preorder的[L.....R]和inorder[L....R]范围内建立出整颗二叉树
        //返回整颗二叉树的头节点
        //加速优化：没必要每次都遍历查找find
        public TreeNode process(int[] preorder, int l, int r, int[] inorder, int L, int R,
        HashMap<Integer,Integer> map){
            //base case
            if(l>r){
                return null;
            }
            TreeNode head=new TreeNode(preorder[l]);
            if(l==r){
                return head;
            }
            int find=map.get(preorder[l]);
            head.left=process(preorder,l+1,l+find-L,inorder,L,find-1,map);
            head.right=process(preorder,r-(R-find)+1,r,inorder,find+1,R,map);
            return head;
        }
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            if(preorder==null||inorder==null||preorder.length!=inorder.length){
                return null;
            }
            int N=preorder.length;
            //准备一个哈希表，记录中序遍历数组中每一个数值所对应的下标
            HashMap<Integer,Integer> valueIndexMap=new HashMap<>();
            for(int i=0;i<N;i++){
                valueIndexMap.put(inorder[i],i);
            }
            return process(preorder,0,N-1,inorder,0,N-1,valueIndexMap);
        }

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

##  ##

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

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

[Link 1]: https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/
[Link 2]: https://leetcode-cn.com/problems/same-tree/
[Link 3]: https://leetcode-cn.com/problems/symmetric-tree/
[Link 4]: https://leetcode-cn.com/problems/balanced-binary-tree/
[Link 5]: https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/