怎么创建自己的游戏网站,百度关键词搜索量查询,织梦响应式茶叶网站模板,岳阳建网站目录
一、题目描述
二、初次解答
三、官方解法
四、总结 一、题目描述 二、初次解答 1. 思路#xff1a;二叉树的先序遍历。首先判断根节点是否是空#xff0c;其次判断根节点是否是叶子节点#xff0c;再者递归获取左子树的深度、右子树的深度#xff0c;最后返回左子…目录
一、题目描述
二、初次解答
三、官方解法
四、总结 一、题目描述 二、初次解答 1. 思路二叉树的先序遍历。首先判断根节点是否是空其次判断根节点是否是叶子节点再者递归获取左子树的深度、右子树的深度最后返回左子树、右子树的最大深度。此题与【LeetCode算法】第111题二叉树的最小深度-CSDN博客类似。 2. 代码 int maxDepth(struct TreeNode* root) {//根节点为空if(!root) return 0;//根节点为叶子节点if(!(root-left) !(root-right)) return 1;int leftDepthmaxDepth(root-left); //递归左子树int rightDepthmaxDepth(root-right); //递归右子树return leftDepthrightDepth?leftDepth1:rightDepth1; //返回左子树和右子树高度最大值
} 3. 优点仅遍历一遍时间复杂度为O(n)。 4. 缺点采用递归算法空间复杂度为O(H), H是二叉树的高度。 三、官方解法 与【LeetCode算法】第111题二叉树的最小深度-CSDN博客类似有广度优先和深度优先与上述解法一致算法。
四、总结
计算二叉树的最大深度和最小深度都可以通过二叉树的先序遍历。只不过最小深度需要额外考虑左子树为空和右子树为空这两个情况。
