海南网站建设网站开发小程序app,丰台手机网站建设,国内网站建设公司top20,网络推广目标怎么写算法学习——LeetCode力扣二叉树篇3 116. 填充每个节点的下一个右侧节点指针
116. 填充每个节点的下一个右侧节点指针 - 力扣#xff08;LeetCode#xff09;
描述
给定一个 完美二叉树 #xff0c;其所有叶子节点都在同一层#xff0c;每个父节点都有两个子节点。二叉树…算法学习——LeetCode力扣二叉树篇3 116. 填充每个节点的下一个右侧节点指针
116. 填充每个节点的下一个右侧节点指针 - 力扣LeetCode
描述
给定一个 完美二叉树 其所有叶子节点都在同一层每个父节点都有两个子节点。二叉树定义如下
struct Node {int val;Node *left;Node *right;Node *next;
}填充它的每个 next 指针让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点则将 next 指针设置为 NULL。
初始状态下所有 next 指针都被设置为 NULL。
示例
示例 1 输入root [1,2,3,4,5,6,7] 输出[1,#,2,3,#,4,5,6,7,#] 解释给定二叉树如图 A 所示你的函数应该填充它的每个 next 指针以指向其下一个右侧节点如图 B 所示。序列化的输出按层序遍历排列同一层节点由 next 指针连接‘#’ 标志着每一层的结束。
示例 2:
输入root [] 输出[]
提示
树中节点的数量在 [0, 212 - 1] 范围内-1000 node.val 1000
进阶
你只能使用常量级额外空间。使用递归解题也符合要求本题中递归程序占用的栈空间不算做额外的空间复杂度。
代码解析
/*
// Definition for a Node.
class Node {
public:int val;Node* left;Node* right;Node* next;Node() : val(0), left(NULL), right(NULL), next(NULL) {}Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}Node(int _val, Node* _left, Node* _right, Node* _next): val(_val), left(_left), right(_right), next(_next) {}
};
*/class Solution {
public:Node* connect(Node* root) {Node* result;Node* node ; //迭代节点queueNode* my_que; //队列if(root nullptr) return root;else // 根节点进队列{my_que.push(root);}while(my_que.empty() ! 1){int size my_que.size(); for(int i0 ; isize ; i) {node my_que.front(); //该层级的点弹出放入数组my_que.pop();if(isize-1)//如果该节点不是该层次的最后一个next指针连接下一个{node-next my_que.front();}else//该节点是该层次的最后一个next连接空{node-next nullptr;}//每一个弹出点的下一个层级左右节点压入队列if(node-left ! nullptr) my_que.push(node-left);if(node-right ! nullptr) my_que.push(node-right);}}return root;}
};
117. 填充每个节点的下一个右侧节点指针 II
117. 填充每个节点的下一个右侧节点指针 II - 力扣LeetCode
描述
给定一个二叉树
struct Node {int val;Node *left;Node *right;Node *next;
}填充它的每个 next 指针让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点则将 next 指针设置为 NULL 。
初始状态下所有 next 指针都被设置为 NULL 。
示例
示例 1
输入root [1,2,3,4,5,null,7] 输出[1,#,2,3,#,4,5,7,#] 解释给定二叉树如图 A 所示你的函数应该填充它的每个 next 指针以指向其下一个右侧节点如图 B 所示。序列化输出按层序遍历顺序由 next 指针连接‘#’ 表示每层的末尾。
示例 2
输入root [] 输出[]
提示
树中的节点数在范围 [0, 6000] 内 -100 Node.val 100
进阶
你只能使用常量级额外空间。使用递归解题也符合要求本题中递归程序的隐式栈空间不计入额外空间复杂度。
代码解析
/*
// Definition for a Node.
class Node {
public:int val;Node* left;Node* right;Node* next;Node() : val(0), left(NULL), right(NULL), next(NULL) {}Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}Node(int _val, Node* _left, Node* _right, Node* _next): val(_val), left(_left), right(_right), next(_next) {}
};
*/class Solution {
public:Node* connect(Node* root) {queueNode* my_que; if( root nullptr ) return root;else my_que.push(root);while(my_que.size() ! 0){int size my_que.size();for(int i0 ; isize ;i){Node* tmp_node my_que.front();my_que.pop();if(i size-1) tmp_node-next nullptr;else tmp_node-next my_que.front();if(tmp_node-left ! nullptr) my_que.push(tmp_node-left);if(tmp_node-right ! nullptr) my_que.push(tmp_node-right);}}return root;}
};
104. 二叉树的最大深度
104. 二叉树的最大深度 - 力扣LeetCode
描述
给定一个二叉树 root 返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例
示例 1
输入root [3,9,20,null,null,15,7] 输出3
示例 2
输入root [1,null,2] 输出2
提示
树中节点的数量在 [0, 104] 区间内。-100 Node.val 100
代码解析
层次遍历
/*** 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:int maxDepth(TreeNode* root) {TreeNode* node ; //迭代节点queueTreeNode* my_que; //队列int result 0;if(root nullptr) return result;else // 根节点进队列{my_que.push(root);}while(my_que.empty() ! 1){int size my_que.size();result 1;//计算层级数量for(int i0 ; isize ; i) {node my_que.front(); //该层级的点弹出放入数组my_que.pop();//每一个弹出点的下一个层级左右节点压入队列if(node-left ! nullptr) my_que.push(node-left);if(node-right ! nullptr) my_que.push(node-right);}}return result;}
};
递归遍历
/*** 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:int getdepth(TreeNode* root){if(rootnullptr) return 0;int left_depth getdepth(root-left);int right_depth getdepth(root-right);return 1max(left_depth , right_depth);}int maxDepth(TreeNode* root) {if(root nullptr) return 0;return getdepth(root);}
};
111. 二叉树的最小深度
111. 二叉树的最小深度 - 力扣LeetCode
描述
给定一个二叉树找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明叶子节点是指没有子节点的节点。
示例
示例 1
输入root [3,9,20,null,null,15,7] 输出2 示例 2
输入root [2,null,3,null,4,null,5,null,6] 输出5
提示
树中节点数的范围在 [0, 105] 内-1000 Node.val 1000
代码解析
层次遍历
/*** 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:int minDepth(TreeNode* root) {TreeNode* node ; //迭代节点queueTreeNode* my_que; //队列int result 0;vectorint min_num;if(root nullptr) return result;else // 根节点进队列{my_que.push(root);}while(my_que.empty() ! 1){int size my_que.size();result 1;for(int i0 ; isize ; i) {node my_que.front(); //该层级的点弹出放入数组my_que.pop();// coutnode-val node-left node-rightendl;//每一个弹出点的下一个层级左右节点压入队列if(node-left ! nullptr) my_que.push(node-left);if(node-right ! nullptr) my_que.push(node-right);//找到叶子节点if(node-left nullptr node-right nullptr) min_num.push_back(result);}}//排序找到叶子节点所在最小层sort(min_num.begin(),min_num.end());return min_num[0];}
};
递归法
/*** 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:int getdepth(TreeNode* cur){if(cur nullptr) return 0;int right_depth , left_depth;//左子树为空直接测量右子树if(cur-left nullptr cur-right ! nullptr){right_depth getdepth(cur-right);return 1 right_depth;}else if(cur-left ! nullptr cur-right nullptr) //右子树为空直接测量左子树{left_depth getdepth(cur-left);return 1 left_depth;}else//左右子树都为空或都不为空左右子树均测量返回最小值{left_depth getdepth(cur-left);right_depth getdepth(cur-right);return 1 min(left_depth,right_depth);}}int minDepth(TreeNode* root) {if(root nullptr) return 0;return getdepth(root);}
};
