剑指Offer55:二叉树的深度&&leetcode110平衡二叉树的深度

清疚 2022-01-31 17:13 224阅读 0赞

**主要题目leetcode:**

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

> 一个二叉树*每个节点* 的左右两个子树的高度差的绝对值不超过1。

给定二叉树 `[3,9,20,null,null,15,7]`

3
       / \
      9  20
        /  \
       15   7

返回 `true` 。  
  
**示例 2:**

给定二叉树 `[1,2,2,3,3,null,null,4,4]`

1
          / \
         2   2
        / \
       3   3
      / \
     4   4

返回 `false` 。

先讲剑指Offer55:求二叉树的深度：题目就是输入一棵二叉树的根节点，求该树的深度。从根节点依次到叶节点依次经过的节点形成树的一条路径，最长路径的长度为树的深度。

解析一下题目：为了啥？输入一个节点后得到一个二叉树的深度，注意是最长。

而一般处理二叉树都用递归的方法比较方便。

递归三件套：

1.递归的终点：即如果if(root == null)return 0;

2.返回值：因为题目需要求出二叉树的深度，深度是一个Int值，所以当前的函数模型的返回值就是public int xxx()\{\}；

3.单次递归需要做的事：从宏观上讲，就root,root.left,root.right.这3个节点，但是一定要把握好第一次正确性，就是完成第一次递归就能达到的效果。因为递归就是不断调用自身，所以第一次递归的结果完成就代表着所有情况的结束，所以你要完成的事就该保证第一次完成时，结果完成。

这里是单次返回左右节点最大的一个并且+1.就是 return (left>right?left:right)+1;

代码：

public int dept(TreeNode root){
    
        if(root == null)
        return 0;
        
        int left = dept(root.left);
        int right = dept(root.right);
        return left>right?left+1:right+1;
    }

**leetcode 上面的110题：**

**判断给定的一棵树是否是平衡二叉树.**

那么所求得即是给定的root根节点的树 是一棵二叉树和不是一棵二叉树，那么需要返回的信息是布尔类型。

宏观上判断一个root节点的树是不是平衡二叉树，那么从root,节点开始判断root.left的左子树是不是平衡二叉树，root.right的右子树是不是平衡二叉树，再最后根据左右子树的节点值来判断root是不是平衡二叉树。

思考的时候就是 宏观把握当前节点就好了

递归的终止条件：就是当前的root==null,return true.

递归的返回值： 就返回当前左。右子树都是平衡的情况下，左，右子树的深度差满足条件就返回true，不满足返回false。(**但是这些信息包括了 当前节点的左子树和右子树的节点值。就是递归返回的信息不单单是布尔值，还要包含节点的值信息，所以这里需要再开辟一个函数来返回节点的值，根据节点的值来返回当前的布尔值。**)

单次递归：根据递归的返回值需要判断左右子树的深度，所以需要再开一个函数来判断当前传入的节点的深度值。往往就是递归要写2个函数的原因，**因为，当前递归的返回信息，需要根据其他信息来判断，开一个新函数导致可以拿到我们想要的信息。**

就先判断左子树是否是平衡二叉树，再右子树是不是平衡二叉树，满足这2个条件下，再判断左右子树的深度差，来判断。

附带代码:

public boolean isBalanced(TreeNode root) {
            
            if(root == null)
                return true;
            //先左后右
            if(isBalanced(root.left)&& isBalanced(root.right)){ 
                int left = dept(root.left);
                int right = dept(root.right);
                 
                if(Math.abs(left-right)<=1)
                    return true;
            }
            
            return false;
            
        }
        
        //返回当前节点的深度
        public int dept(TreeNode root)
        {
            
            if(root == null){
                
                return 0;
            }
            
            int left = dept(root.left);
            
            int right = dept(root.right);
            
        
            
            return Math.max(left,right)+1;
        }