手机网站优化排名,php网站开发外包,网页设计与应用论文,刷赞网站怎么做力扣日记#xff1a;【二叉树篇】二叉树的最大深度 日期#xff1a;2023.11.27 参考#xff1a;代码随想录、力扣 104. 二叉树的最大深度
题目描述 难度#xff1a; 给定一个二叉树 root #xff0c;返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最…力扣日记【二叉树篇】二叉树的最大深度 日期2023.11.27 参考代码随想录、力扣 104. 二叉树的最大深度
题目描述 难度 给定一个二叉树 root 返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 示例 1 输入root [3,9,20,null,null,15,7] 输出3 示例 2 输入root [1,null,2] 输出2 提示
树中节点的数量在 [0, 10^4] 区间内。-100 Node.val 100
题解
递归法(cpp ver)
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:// 递归法后序遍历 (实际上是求高度)// 1. 确定递归函数的参数和返回值参数就是传入树的根节点返回就返回以该节点为根的树的深度int getdepth(TreeNode* node) { // 2. 确定终止条件如果为空节点的话就返回0表示高度为0。if (node NULL) return 0;// 3. 确定单层递归的逻辑先求它的左子树的深度再求右子树的深度最后取左右深度最大的数值 再1 加1是因为算上当前中间节点就是目前节点为根节点的树的深度。int leftdepth getdepth(node-left); // 左(左子树的高度)int rightdepth getdepth(node-right); // 右(右子树的高度)int depth 1 max(leftdepth, rightdepth); // 中(左子树和右子树的根节点的高度, 包括根节点, 故1)return depth;}int maxDepth(TreeNode* root) {return getdepth(root);}
};迭代法(go ver)
/*** Definition for a binary tree node.* type TreeNode struct {* Val int* Left *TreeNode* Right *TreeNode* }*/
func maxDepth(root *TreeNode) int {// 使用迭代法的话使用层序遍历是最为合适的因为最大的深度就是二叉树的层数和层序遍历的方式极其吻合queue : list.New()maxDepth : 0if root ! nil {queue.PushBack(root)}for queue.Len() 0 {// 记录当前队列长度size : queue.Len()for size 0 {// 弹出并写入结果front : queue.Front()node : queue.Remove(front).(*TreeNode) // 存进list之后类型会变为*list.Element要转换为*TreeNode// 左右节点入队列if node.Left ! nil {queue.PushBack(node.Left)}if node.Right ! nil {queue.PushBack(node.Right)}size - 1}maxDepth 1}return maxDepth
}复杂度
时间复杂度 空间复杂度
思路总结
本题如果用迭代法则直接使用层序遍历的模板解题即可如果用递归法则相对难一些 首先要理解二叉树的深度和高度区别 二叉树节点的深度指从根节点到该节点的最长简单路径边的条数或者节点数取决于深度从0开始还是从1开始—— 即深度是从某节点角度往上根节点看的二叉树节点的高度指从该节点到叶子节点的最长简单路径边的条数或者节点数取决于高度从0开始还是从1开始—— 即高度是从某节点角度往下叶子节点看的因此根节点的高度就是二叉树的最大深度 本题可以使用前序中左右也可以使用后序遍历左右中使用前序求的就是深度即最大的叶子节点深度使用后序求的是高度即根节点的高度。后序遍历相对容易理解一些见代码
