剑指offer-38、⼆叉树的深度
<h2 id="题描述">题⽬描述</h2><p>输⼊⼀棵⼆叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的⼀条路径，最⻓路径的⻓度为树的深度。</p>
<p>示例1<br>
输⼊：{1,2,3,4,5,#,6,#,#,7}<br>
返回值：4</p>
<h2 id="思路及解答">思路及解答</h2>
<p>声明：这⾥的输⼊是⼀个数的根节点，也就是从根节点，我们就可以获取到树的所有节点，⽽类似数组的表达⽅式 {1,2,3,4,5,#,6,#,#,7} ，则是按照层次来放的。(⽐如这个树就是4层)</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202504201725405.png" alt="" loading="lazy"></p>
<h3 id="递归">递归</h3>
<p>第⼀种⽅法⽐较容易想到，对于任意⼀个节点 node ⽽⾔，我要想知道当前 node 节点（包括当前节点）的深度，肯定得求当前节点的左边节点（设为 left ）的深度 leftDeepth ，以及获取右节点（设为 right ）的深度 rightDeepth ，然后求两者最⼤+1（ Max{leftDeepth,rightDeepth}+1 ），就是当前节点的深度。</p>
<p>思路：二叉树的深度 = max(左子树深度, 右子树深度) + 1</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202504201726110.png" alt="" loading="lazy"></p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202504201726816.png" alt="" loading="lazy"></p>
<p>⽽递归中⽐较重要的⼀点，是结束条件。在这道题中，如果⼀个节点为 null ，就结束，并且当前节点的深度是 0 。代码超级⽆敌短：</p>
<pre><code class="language-java">public class Solution {
public int TreeDepth(TreeNode root) {
if(root==null) return 0;
return Math.max(TreeDepth(root.left),TreeDepth(root.right))+1;
}
}
</code></pre>
<p>以上解法要是看不明白，可以看详细点的：</p>
<pre><code class="language-java">public class Solution {
public int TreeDepth(TreeNode root) {
// 递归终止条件：空节点深度为0
if (root == null) {
return 0;
}
// 递归计算左子树深度
int leftDepth = maxDepth(root.left);
// 递归计算右子树深度
int rightDepth = maxDepth(root.right);
// 当前树深度 = 左右子树最大深度 + 1（当前节点）
return Math.max(leftDepth, rightDepth) + 1;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，需要访问每个节点一次</li>
<li><strong>空间复杂度</strong>：O(h)，递归栈深度等于树高，最坏情况（链表）为O(n)</li>
</ul>
<h3 id="迭代遍历">迭代遍历</h3>
<p>思路是如果树的根节点不为空，则将根节点放进队列中。也就是，每遍历一层，深度加1，直到遍历完所有层</p>
<p>设置深度 deep 为0。使⽤ while 循环，只要队列不为空，则执⾏下⾯操作：</p>
<ol>
<li>获取队列的⼤⼩ size 。</li>
<li>依次取出队列的前 size 个元素，如果该元素的左边节点不为空，则将左边节点放进队列，如果该元素的右边节点不为空，则将该元素的右边节点放进队列。</li>
<li>层次 deep+1</li>
</ol>
<pre><code class="language-java">public class Solution {
public int TreeDepth(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int depth = 0;
while (!queue.isEmpty()) {
// 当前层的节点个数
int levelSize = queue.size();
// 遍历当前层的所有节点
for (int i = 0; i < levelSize; i++) {
TreeNode currentNode = queue.poll();
// 将下一层节点加入队列
if (currentNode.left != null) {
queue.offer(currentNode.left);
}
if (currentNode.right != null) {
queue.offer(currentNode.right);
}
}
// 完成一层遍历，深度加1
depth++;
}
return depth;
}
}
</code></pre>
<ul>
<li>时间复杂度为：O(n)，所有的节点需要进⼊队列，再出队列</li>
<li>空间复杂度：O(n),借助了额外的队列空间。</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19226225
頁:
[1]