[剑指offer]面试题第[55-2]题[Leetcode][第110题][JAVA][平衡二叉树][DFS][剪枝]

女爷i 2023-02-22 12:14 51阅读 0赞

#### 【问题描述】\[中等\] ####

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
    
     
    示例 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 。
    
     
    
    限制：
    
    1 <= 树的结点个数 <= 10000

#### 【解答思路】 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]

###### 1. 后序遍历 + 剪枝 （从底至顶） ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]  
**时间复杂度：O(N) 空间复杂度：O(N)**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]

class Solution { 
        public boolean isBalanced(TreeNode root) { 
            return recur(root) != -1;
        }
    
        private int recur(TreeNode root) { 
            if (root == null) return 0;
            int left = recur(root.left);
            if(left == -1) return -1;
            int right = recur(root.right);
            if(right == -1) return -1;
            return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
        }
    }

###### 2. 先序遍历 + 判断深度 （从顶至底） ######

**时间复杂度：O(NlogN) 空间复杂度：O(N)**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]

public boolean isBalanced(TreeNode root) { 
            if(root == null) return true;
            int l = maxDepth(root.left);
            int r = maxDepth(root.right);
            if(Math.abs(r-l)>1){ 
                return false;
            }
            else{ 
                return isBalanced(root.left) && isBalanced(root.right);
            }
            
    
    
        }
        public int maxDepth(TreeNode root) { 
            if(root == null) return 0;
            return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
        }

#### 【总结】 ####

###### 1.树的遍历方式总体分为两类：深度优先搜索（DFS）、广度优先搜索（BFS）； ######

常见的 DFS ： 先序遍历、中序遍历、后序遍历；  
常见的 BFS ： 层序遍历（即按层遍历）。

###### 2.二叉树遍历 ######

*  前序遍历 先输出当前结点的数据，再依次遍历输出左结点和右结点
 *  中序遍历 先遍历输出左结点，再输出当前结点的数据，再遍历输出右结点
 *  后续遍历 先遍历输出左结点，再遍历输出右结点，最后输出当前结点的数据

###### 3. 审题 任意节点 遍历所有情况 切忌想当然 ######

转载链接：https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/solution/mian-shi-ti-55-ii-ping-heng-er-cha-shu-cong-di-zhi/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200703132824633.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020070313284551.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200703132906234.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200703133116527.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70