数据结构与算法--二叉树的深度问题

绝地灬酷狼 2022-10-10 01:27 169阅读 0赞

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

*  题目：输入一颗二叉树的根，求该树的深度。从根节点到叶子节点一次进过的节点形成的一条路径，最长的路径的长度为树的深度。
 *  如下图中二叉树的额深度4，因为从根节点A到叶子节点的路径中有4个节点A B E J

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

*  问题中定义了一种树深度的计算规则，我们根据这个定义去得到树所有的路径，也就得到了最长的额路径。在我们之前的文章：[数据结构与算法–面试必问AVL树原理及实现][AVL]文章中，我们对二叉搜索树的具体实现方案有详细的说明，其中二叉搜索树平衡条件是左右子树的高度差不能超过1 ，和我们当前要求是一致的，我们借鉴其中高度求值的思路
 *  分析
    
     *  二叉树还是递归的思路，既然我们需要求高度差
     *  分别递归求左右子树的高度，在求解
     *  同二叉树的后续遍历一样递归，只不是现在将遍历元素值，变为现在遍历高度并累加
     *  递归思路，按最简单的节点分析，当只有一个左右子树，那么递归到left 高度0， 递归到right 高度0
     *  那么此时根节点高度 height= Math.max(left + right) + 1
 *  经如上分析有如下代码

#### 变种题型-求平衡二叉树 ####

*  题目：输入一颗二叉树的根，判断该树是否平衡二叉树。如果某二叉树中任意左右节点的树深度不超过1 ，那么他就是一颗平衡二叉树。
 *  还是在刚才二叉搜索树的文中，我们求高度的目的就是需要再平衡二叉树，使得经过修改的二叉树能够达到二叉搜索树的结构特性。既然在以上方法中我们得到了高度，那么可以在逻辑上修改就能求解本问题
 *  分析：
    
     *  通上题中，分别递归求解left， right
     *  得到left， right高度，求差值 > 1 ,则不是平衡
 *  如上分析有如下代码：

/** * 求二叉树的深度 * @author liaojiamin * @Date:Created in 17:43 2021/6/24 */
    public class BinaryDepth { 
    
        public static void main(String[] args) { 
            BinaryNode node1 = new BinaryNode(null, null, null);
            BinarySearchTree tree1 = new BinarySearchTree();
            Random random = new Random();
            int[] array = new int[]{ 1,27,37,19,514,216,118,320,426,228};
            for (int i = 0; i < array.length; i++) { 
                node1 = tree1.insert(Integer.valueOf(random.nextInt(20)), node1);
            }
            System.out.println(validateBalancedTree(node1));
            tree1.printTree(node1);
        }
    
    
        /** * 一棵二叉树中所有节点对应的左右子树高度差不超过1 ，那么说明这棵树是平衡二叉树 * 递归判断是否平衡树 * */
        public static boolean validateBalancedTree(BinaryNode tree){ 
            if(tree == null){ 
                return true;
            }
            int left = depthBinary(tree.getLeft());
            int right = depthBinary(tree.getRight());
            int diff = Math.abs(left - right);
            if(diff > 1){ 
                return false;
            }
            return validateBalancedTree(tree.getLeft()) && validateBalancedTree(tree.getRight());
        }
       /** * 递归方式求解， * 左节点为空则，左高度为left = 0，总高度为 left + 1 * 右节点为空则，右高度为right = 0，总高度为 right + 1 * 递归到子节点，赋值left= 0，right = 0，接着一层一层递归上到根节点。 * */
        public static Integer depthBinary(BinaryNode tree){ 
            if(tree == null){ 
                return 0;
            }
            int left = depthBinary(tree.getLeft());
            int right = depthBinary(tree.getRight());
            return left > right ? left + 1 : right + 1;
        }
    }

*  以上代码比较简单，但是存在问题是节点会被重复遍历，当遍历第二层节点 B，C时候，会遍历H I J节点，同样 遍历D，E F G时候还是会重复遍历H I J 节点，类似斐波那契数量的递归求解一样，重复的遍历会时间复杂度指数级增长，当树高度越大，重复遍历的次数越多。我们需要找到更优方案

#### 每个节点遍历一次解法 ####

*  我们之前是为了求深度，才直接递归左右节点，然后在判断，既然我们都遍历了求出了深度，那么能不能同时标记每一个节点的深度呢
 *  分析
    
     *  还是按刚才思路，分别遍历左右子树求高度，我们还是按最简单的元素来分析递归的情况
     *  当左右子树都只有一个节点，遍历左子树，left = 1， 遍历右子树 right = 1
     *  此时不同的点我们更新当前根节点的高度height = Math.max（left，right） + 1
     *  依次递归到根节点
     *  以上思路还是二叉树的后续遍历的思想，左右根，一边遍历，一边计算高度，一边更新节点高度信息
     *  更新完根的高度后，在判断是否满足 left - right > 1,放回对应值，以跳出递归
 *  如是哪个分析有如下代码

/** * 求二叉树的深度 * @author liaojiamin * @Date:Created in 17:43 2021/6/24 */
    public class BinaryDepth { 
    
        public static void main(String[] args) { 
            BinaryNode node1 = new BinaryNode(null, null, null);
            BinarySearchTree tree1 = new BinarySearchTree();
            Random random = new Random();
            int[] array = new int[]{ 1,27,37,19,514,216,118,320,426,228};
            for (int i = 0; i < array.length; i++) { 
                node1 = tree1.insert(Integer.valueOf(random.nextInt(20)), node1);
            }
            System.out.println(validateBalancedTreeHeight(node1));
            tree1.printTree(node1);
        }
    
     /** * 直接后序遍历，同时标记深度 * */
        public static boolean validateBalancedTreeHeight(BinaryNode tree){ 
            if(tree == null){ 
                return true;
            }
            boolean left = validateBalancedTreeHeight(tree.getLeft());
            boolean right = validateBalancedTreeHeight(tree.getRight());
            int leftHeight = tree.getLeft()!= null ? tree.getLeft().getHeight(): 0;
            int rightHeight = tree.getRight() != null ? tree.getRight().getHeight() : 0;
            tree.setHeight(1 + Math.max(leftHeight, rightHeight));
            if(left && right){ 
                int diff = Math.abs(leftHeight - rightHeight);
                if(diff > 1){ 
                    return false;
                }else { 
                    return true;
                }
            }
            return false;
        }
     }

*  以上方法后续遍历的方式遍历整个二叉树，遍历同时求深度，判断平衡，当遍历到树根，也就得树是否平衡的二叉树。

[上一篇：数据结构与算法–数字在排序数组中出现次数][Link 1]  
[下一篇：数据结构与算法–数组中出一次的数字][Link 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpYW9qaWFtaW4wMTAy_size_16_color_FFFFFF_t_70]: /images/20221005/6e65d59c3240457b9e4bf2d6b4c43209.png
[AVL]: https://blog.csdn.net/liaojiamin0102/article/details/111294831
[Link 1]: https://blog.csdn.net/liaojiamin0102/article/details/118191713
[Link 2]: https://blog.csdn.net/liaojiamin0102/article/details/118311083