“二叉树的深度”和“平衡二叉树”

末蓝、 2022-05-13 02:03 283阅读 0赞

## 题目描述 ##

二叉树的深度：

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

二叉树的节点定义如下：

public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
        }
    
    }

二叉树的深度就是根节点的深度（值为1）加上左、右子树深度的最大值，递归求解就好了。

public class Solution {
        public int TreeDepth(TreeNode root) {
        if(root==null){
        	  return 0;
          }else{
          return Math.max(TreeDepth(root.left),TreeDepth(root.right))+1;}   
        }
    }

如果这个二叉树的节点值个数n，那么该算法的时间复杂度为**O(n)**。

和求二叉树深度类似的一个题目就是判断一棵树是否为平衡二叉树。

## 题目描述 ##

输入一棵二叉树，判断该二叉树是否为平衡二叉树。

有了求二叉树的深度的经验之后再解决这个问题，我们很容易就能想到一种思路：在遍历树的每个节点的时候，调用求“二叉树的深度”的函数得到节点的左、右子树的深度。如果每个节点的左、右子树的深度都不超过1，那么按照定义它就是一棵平衡二叉树。假如要判断的二叉树的结构如下：

![70][]

这种思路对应的判断一棵树时候为平衡二叉树的代码如下：

public class Solution2 {
        private static boolean isBalanced=true;
        public static void main(String[] args) {
            TreeNode node1 = new TreeNode(1);
            TreeNode node2 = new TreeNode(1);
            TreeNode node3 = new TreeNode(1);
            TreeNode node4 = new TreeNode(1);
            TreeNode node5 = new TreeNode(1);
            TreeNode node6 = new TreeNode(1);
            TreeNode node7 = new TreeNode(1);
            node1.left = node2;
            node1.right = node3;
            node2.left = node4;
            node2.right = node5;
            node3.right = node6;
            node5.left = node7;
            Long begintime = System.nanoTime();
            boolean res = IsBalanced_Solution(node1);
            Long endtime = System.nanoTime();
            System.out.println("该二叉树是否为平衡二叉树："+res+",运行时间："+(endtime - begintime) + "ns");
    
        }
       public static boolean IsBalanced_Solution(TreeNode root) {
            if(root==null){
                return true;
            }else{
                return Math.abs(getDepth(root.left)-getDepth(root.right))<=1 && IsBalanced_Solution(root.left)
                        && IsBalanced_Solution(root.right);
            }
        }
        public static int getDepth(TreeNode root){
            if(root==null){
                return 0;
            }else{
                return Math.max(getDepth(root.left),getDepth(root.right))+1;
            }
        }
    }

程序运行结果：

![70 1][]

上面的代码固然简洁，但我们也要注意到由于一个节点会被重复遍历多次，这种思路的时间效率不高。例如，在函数IsBalanced\_Solution( )中输入最上面图中的二叉树，我们将首先判断根节点（节点1）是不是平衡的。此时我们往函数getDepth( )里输入左子树的根节点（节点2）时，需要遍历节点4、5、7。接下来判断以节点2为根节点的子树是不是平衡树的时候，仍然会遍历节点4、5、7。毫无疑问，重复遍历同一个节点会影响性能。接下来我们寻找不需要重复遍历的算法。

如果我们以后续遍历的方式遍历二叉树的每一个节点，那么在便利到一个节点之前我们就已经遍历了它的左、右子树。只要在遍历每个节点的时候记录它的深度（某一节点的深度等于她到叶子节点的路径的长度），我们就可以一边遍历一边判断每个节点是不是平衡的。下面是这种思路的实现代码：

public class Solution {
        //后续遍历时，遍历到一个节点，其左右子树已经遍历  依次自底向上判断，每个节点只需要遍历一次
        private static boolean isBalanced=true;
        public static void main(String[] args) {
            TreeNode node1 = new TreeNode(1);
            TreeNode node2 = new TreeNode(2);
            TreeNode node3 = new TreeNode(3);
            TreeNode node4 = new TreeNode(4);
            TreeNode node5 = new TreeNode(5);
            TreeNode node6 = new TreeNode(6);
            TreeNode node7 = new TreeNode(7);
            node1.left = node2;
            node1.right = node3;
            node2.left = node4;
            node2.right = node5;
            node3.right = node6;
            node5.left = node7;
            Long begintime = System.nanoTime();
            boolean res = IsBalanced_Solution(node1);
            Long endtime = System.nanoTime();
            System.out.println("该二叉树是否为平衡二叉树："+res+",运行时间："+(endtime - begintime) + "ns");
    
        }
    
        public static boolean IsBalanced_Solution(TreeNode root) {
            getDepth(root);
            return isBalanced;
        }
        public static int getDepth(TreeNode root){
            if(root==null)
                return 0;
            int left=getDepth(root.left);
            int right=getDepth(root.right);
    
            if(Math.abs(left-right)>1){
                isBalanced=false;
            }
            return right>left ?right+1:left+1;
    
        }
    }

程序运行结果：

![70 2][]

可以看到，同样的二叉树，第二种方法判断二叉树是否为平衡二叉树的运行时间变短了。

在上面的代码中，我们用后续遍历的方式遍历整棵二叉树。在遍历某节点的左、右子节点之后，我们可以根据它的左、右子节点的深度判断它是不是平衡的，并得到当前节点的深度。当最后遍历到树的根节点的时候，也就判断了整棵二叉树是不是平衡二叉树。如果这个二叉树的节点个数为n，那么该算法对每个节点只遍历了一次，时间复杂度也就是**O(n)。**

[70]: /images/20220513/38e936fc91f0442b9937142f9ec3179f.png
[70 1]: /images/20220513/63028668bee144e5a48944e4ae7c712b.png
[70 2]: /images/20220513/493c41a153ff47be8a781c0e59ef10d2.png