一个网站需要哪些备案,网站备案在线注销,wordpress记录点击数,商场设计规范深度优先搜索#xff08;DFS#xff09;是一种常用的递归算法#xff0c;用于解决树形结构的问题。在计算二叉树的最大深度时#xff0c;DFS方法会从根节点开始#xff0c;递归地计算左右子树的最大深度#xff0c;然后在返回时更新当前节点所在路径的最大深度。
如果我… 深度优先搜索DFS是一种常用的递归算法用于解决树形结构的问题。在计算二叉树的最大深度时DFS方法会从根节点开始递归地计算左右子树的最大深度然后在返回时更新当前节点所在路径的最大深度。
如果我们知道了左子树和右子树的最大深度 left 和 right那么该二叉树的最大深度即为 max(left ,right)1
递归实现
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val* this.left left;* this.right right;* }* }*/
class Solution {// 定义一个方法递归地计算二叉树的最大深度public int maxDepth(TreeNode root) {// 如果根节点为空则返回0树的高度为0if(root null) return 0;// 递归地计算左子树的最大深度int left maxDepth(root.left);// 递归地计算右子树的最大深度int right maxDepth(root.right);// 返回左子树和右子树中的最大深度加上当前节点的高度1return Math.max(left,right)1;}
}
二叉树的最大深度可以使用广度优先搜索BFS来求解而且可以通过修改BFS的方式来实现。这种方法与之前提到的BFS方法的区别在于它是逐层地遍历二叉树而不是逐个节点地遍历。
迭代实现
class Solution {// 定义一个队列用于广度优先搜索BFSQueueTreeNode que new LinkedList();public int maxDepth(TreeNode root) {// 如果根节点为空则返回0树的高度为0if(root null) return 0;// 将根节点加入队列que.offer(root);// 初始化结果变量为0用于记录最大深度int res 0;// 当队列不为空时执行循环while(!que.isEmpty()){// 获取队列的当前大小用于下面的循环控制int size que.size();// 当队列中还有节点时执行循环while(size 0){// 从队列中取出一个节点TreeNode node que.poll();// 如果当前节点的左子节点不为空将其加入队列if(node.left ! null){que.offer(node.left);}// 如果当前节点的右子节点不为空将其加入队列if(node.right ! null){que.offer(node.right);}// 队列大小减1因为已经取出了一个节点size--;}// 结果变量加1表示高度增加了res;}// 返回计算出的最大深度return res;}
}
