成都企业网站建设费用,网站开发软件中文版,怎么做网站外链,凡科网站能在百度做推广吗二叉树的深度
题目#xff1a;输入一颗二叉树的根#xff0c;求该树的深度。从根节点到叶子节点一次进过的节点形成的一条路径#xff0c;最长的路径的长度为树的深度。如下图中二叉树的额深度4#xff0c;因为从根节点A到叶子节点的路径中有4个节点A B E J 问题中定义了一…二叉树的深度
题目输入一颗二叉树的根求该树的深度。从根节点到叶子节点一次进过的节点形成的一条路径最长的路径的长度为树的深度。如下图中二叉树的额深度4因为从根节点A到叶子节点的路径中有4个节点A B E J 问题中定义了一种树深度的计算规则我们根据这个定义去得到树所有的路径也就得到了最长的额路径。在我们之前的文章数据结构与算法–面试必问AVL树原理及实现文章中我们对二叉搜索树的具体实现方案有详细的说明其中二叉搜索树平衡条件是左右子树的高度差不能超过1 和我们当前要求是一致的我们借鉴其中高度求值的思路分析 二叉树还是递归的思路既然我们需要求高度差分别递归求左右子树的高度在求解同二叉树的后续遍历一样递归只不是现在将遍历元素值变为现在遍历高度并累加递归思路按最简单的节点分析当只有一个左右子树那么递归到left 高度0 递归到right 高度0那么此时根节点高度 height Math.max(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(depthBinary(node1));tree1.printTree(node1);}
/*** 递归方式求解* 左节点为空则左高度为left 0总高度为 left 1* 右节点为空则右高度为right 0总高度为 right 1* 递归到子节点赋值left 0right 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;}
}变种题型-求平衡二叉树
题目输入一颗二叉树的根判断该树是否平衡二叉树。如果某二叉树中任意左右节点的树深度不超过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 0right 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;}
}
以上代码比较简单但是存在问题是节点会被重复遍历当遍历第二层节点 BC时候会遍历H I J节点同样 遍历DE F G时候还是会重复遍历H I J 节点类似斐波那契数量的递归求解一样重复的遍历会时间复杂度指数级增长当树高度越大重复遍历的次数越多。我们需要找到更优方案
每个节点遍历一次解法
我们之前是为了求深度才直接递归左右节点然后在判断既然我们都遍历了求出了深度那么能不能同时标记每一个节点的深度呢分析 还是按刚才思路分别遍历左右子树求高度我们还是按最简单的元素来分析递归的情况当左右子树都只有一个节点遍历左子树left 1 遍历右子树 right 1此时不同的点我们更新当前根节点的高度height Math.maxleftright 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;}}以上方法后续遍历的方式遍历整个二叉树遍历同时求深度判断平衡当遍历到树根也就得树是否平衡的二叉树。
上一篇数据结构与算法–数字在排序数组中出现次数 下一篇数据结构与算法–数组中出一次的数字
