有专业做网站,视频链接生成网站,国际新闻最新,wordpress破解防盗链LeetCode 513.找树左下角的值
1、题目
题目链接#xff1a;513. 找树左下角的值 给定一个二叉树的 根节点 root#xff0c;请找出该二叉树的 最底层 最左边 节点的值。 假设二叉树中至少有一个节点。
示例 1:
输入: root [2,1,3]
输出: 1示例 2:
输入: [1,2,3,4,null…LeetCode 513.找树左下角的值
1、题目
题目链接513. 找树左下角的值 给定一个二叉树的 根节点 root请找出该二叉树的 最底层 最左边 节点的值。 假设二叉树中至少有一个节点。
示例 1:
输入: root [2,1,3]
输出: 1示例 2:
输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7提示:
二叉树的节点个数的范围是 [1,104]-231 Node.val 231 - 1
2、深度优先搜索递归
思路
这道题要在二叉树的 最后一行 找到 最左边的值。 如果使用递归法如何判断是最后一行呢其实就是深度最大的叶子节点一定是最后一行。所以要找深度最大的叶子节点。 那么如何找最左边的呢可以使用前序遍历当然中序后序都可以因为本题没有中间节点的处理逻辑只要左优先就行保证优先左边搜索然后记录深度最大的叶子节点此时就是树的最后一行最左边的值。 我们使用 maxDepth 用来记录最大深度result 记录最大深度最左节点的数值。 在写递归时我们要先明确递归三部曲
确定递归函数的参数和返回值
参数必须有要遍历的树的根节点depth 用来记录当前深度maxDepth 用来记录最大深度result 记录最大深度最左节点的数值。 这里就不需要返回值了所以递归函数的返回类型为 void。 代码如下
void traversal(TreeNode* root, int depth, int maxDepth, int result)确定终止条件
当遇到叶子节点的时候就需要统计一下最大的深度了所以需要遇到叶子节点来更新最大深度。 代码如下
// 如果当前节点是叶子节点
if (root-left nullptr root-right nullptr) {// 如果当前深度大于最大深度if (depth maxDepth) {// 更新最大深度maxDepth depth;// 更新结果值为当前节点的值result root-val;}return;
}确定单层递归的逻辑
在找最大深度的时候递归的过程中依然要使用回溯。 代码如下
// 如果左子节点存在
if (root-left) {// 深度加1depth;// 递归遍历左子树traversal(root-left, depth, maxDepth, result);// 回溯深度减1depth--;
}
// 如果右子节点存在
if (root-right) {// 深度加1depth;// 递归遍历右子树traversal(root-right, depth, maxDepth, result);// 回溯深度减1depth--;
}代码
#include iostream
#include climitsusing namespace std;//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:void traversal(TreeNode* root, int depth, int maxDepth, int result) {// 如果当前节点是叶子节点if (root-left nullptr root-right nullptr) {// 如果当前深度大于最大深度if (depth maxDepth) {// 更新最大深度maxDepth depth;// 更新结果值为当前节点的值result root-val;}return;}// 如果左子节点存在if (root-left) {// 深度加1depth;// 递归遍历左子树traversal(root-left, depth, maxDepth, result);// 回溯深度减1depth--;}// 如果右子节点存在if (root-right) {// 深度加1depth;// 递归遍历右子树traversal(root-right, depth, maxDepth, result);// 回溯深度减1depth--;}return;}int findBottomLeftValue(TreeNode* root) {if (root nullptr) {return 0;}// 记录最大深度int maxDepth INT_MIN;// 记录最大深度最左节点的数值int result 0;traversal(root, 0, maxDepth, result);return result;}
};int main() {Solution s;TreeNode* root new TreeNode(3);root-left new TreeNode(9);root-right new TreeNode(20);root-right-left new TreeNode(15);root-right-right new TreeNode(7);cout s.findBottomLeftValue(root) endl;return 0;
}复杂度分析
时间复杂度: O(n)其中 n 是二叉树的节点数目。需要遍历 n 个节点。空间复杂度: O(n)。递归栈需要占用 O(n) 的空间。
3、深度优先搜索递归精简版
思路
在回溯的地方可以进行精简在调用traversal函数时depth加1在递归结束时再减1以确保在递归的不同层次上深度值是正确的。 代码如下 traversal(root-right, depth 1, maxDepth, result);
代码
class Solution {
public:void traversal(TreeNode* root, int depth, int maxDepth, int result) {// 如果当前节点是叶子节点if (root-left nullptr root-right nullptr) {// 如果当前深度大于最大深度if (depth maxDepth) {// 更新最大深度maxDepth depth;// 更新结果值为当前节点的值result root-val;}return;}// 如果左子节点存在if (root-left) {// 递归遍历左子树这里隐藏了回溯操作在调用traversal函数时depth加1在递归结束时再减1traversal(root-left, depth 1, maxDepth, result);}// 如果右子节点存在if (root-right) {// 递归遍历右子树这里隐藏了回溯操作在调用traversal函数时depth加1在递归结束时再减1traversal(root-right, depth 1, maxDepth, result);}return;}int findBottomLeftValue(TreeNode* root) {if (root nullptr) {return 0;}// 记录最大深度int maxDepth INT_MIN;// 记录最大深度最左节点的数值int result 0;traversal(root, 0, maxDepth, result);return result;}
};复杂度分析
时间复杂度: O(n)其中 n 是二叉树的节点数目。需要遍历 n 个节点。空间复杂度: O(n)。递归栈需要占用 O(n) 的空间。
4、广度优先搜索正向层序遍历
思路
使用广度优先搜索遍历每一层的节点。遍历到最后一行的第一个结点就是要找的结点。
代码
class Solution {
public:int findBottomLeftValue(TreeNode* root) {// 如果根节点为空返回0if (root nullptr) {return 0;}// 创建一个队列用于层序遍历queueTreeNode* que;// 记录结果int result 0;// 将根节点入队que.push(root);// 当队列不为空时进行循环while (!que.empty()) {// 获取当前层的节点个数int size que.size();// 遍历当前层的节点for (int i 0; i size; i) {// 取出队首节点TreeNode* node que.front();// 弹出队首节点que.pop();// 如果是当前层的第一个节点更新结果if (i 0) {result node-val;}// 如果该节点有左子节点将左子节点入队if (node-left) {que.push(node-left);}// 如果该节点有右子节点将右子节点入队if (node-right) {que.push(node-right);}}}return result;}
};复杂度分析
时间复杂度: O(n)空间复杂度: O(n)
5、广度优先搜索逆向层序遍历
思路
使用广度优先搜索遍历每一层的节点。在遍历一个节点时需要先把它的非空右子节点放入队列然后再把它的非空左子节点放入队列这样才能保证从右到左遍历每一层的节点。广度优先搜索所遍历的最后一个节点的值就是最底层最左边节点的值。
代码
class Solution {
public:int findBottomLeftValue(TreeNode* root) {// 如果根节点为空返回0if (root nullptr) {return 0;}// 创建一个队列用于层序遍历queueTreeNode* que;// 记录结果int result 0;// 将根节点入队que.push(root);// 当队列不为空时进行循环while (!que.empty()) {// 获取队首节点TreeNode* node que.front();que.pop();// 如果该节点有右子节点将右子节点入队if (node-right) {que.push(node-right);}// 如果该节点有右子节点将右子节点入队if (node-left) {que.push(node-left);}// 更新结果为当前节点的值result node-val;}return result;}
};复杂度分析
时间复杂度: O(n)空间复杂度: O(n)
