【LeetCode】513. 找树左下角的值（中等）——代码随想录算法训练营Day18

本文主要是介绍【LeetCode】513. 找树左下角的值（中等）——代码随想录算法训练营Day18，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：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

文章讲解：代码随想录

视频讲解：怎么找二叉树的左下角？递归中又带回溯了，怎么办？| LeetCode：513.找二叉树左下角的值_哔哩哔哩_bilibili

题解1：递归法

思路：递归的找出树的第1个最大深度的叶子节点，这个节点的值即为树的左下角的值。

/*** Definition for a binary tree node.* function TreeNode(val, left, right) {*     this.val = (val===undefined ? 0 : val)*     this.left = (left===undefined ? null : left)*     this.right = (right===undefined ? null : right)* }*/
/*** @param {TreeNode} root* @return {number}*/
var findBottomLeftValue = function(root) {let maxDepth = 0; // 最大深度let res = 0; // 结果const order = function (node, depth) {if (!node.left && !node.right && depth > maxDepth) {maxDepth = depth;res = node.val;return;}node.left && order(node.left, depth + 1); // 左node.right && order(node.right, depth + 1); // 右}order(root, 1);return res;
};

分析：时间复杂度为 O(n)，空间复杂度为 O(logn)。

题解2：迭代法

思路：使用层序遍历，每次取出每层的第1个元素，最后一层的第1个元素的值即为树的左下角的值。

/*** Definition for a binary tree node.* function TreeNode(val, left, right) {*     this.val = (val===undefined ? 0 : val)*     this.left = (left===undefined ? null : left)*     this.right = (right===undefined ? null : right)* }*/
/*** @param {TreeNode} root* @return {number}*/
var findBottomLeftValue = function(root) {const queue = [root];let res = 0;while (queue.length > 0) {const length = queue.length;for (let i = 0; i < length; i++) {const node = queue.shift();// 取每层的第1个元素if (i === 0) {res = node.val;}node.left && queue.push(node.left);node.right && queue.push(node.right);}}return res;
};

分析：时间复杂度为 O(n)，空间复杂度为 O(n)。