513.找树左下角的值

https://leetcode-cn.com/problems/find-bottom-left-tree-value/

• 513.找树左下角的值

  • 题目描述

  • 方法 1：层次遍历

    • 思路

    • 伪代码

    • 代码(JavaScript/Python/C++)

    • 复杂度分析

  • 方法 2：DFS

    • 思路

    • 伪代码

    • 复杂度分析

    • 代码(JavaScript/Python/C++)

题目描述

给定一个二叉树，在树的最后一行找到最左边的值。

示例 1:

输入:

    2
   / \
  1   3

输出:
1


示例 2:

输入:

        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7

输出:
7


注意: 您可以假设树（即给定的根节点）不为 NULL。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-bottom-left-tree-value
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法 1：层次遍历

思路

按照题目意思我们只需要找到最后一层，返回最左边的节点即可。

所以只要对二叉树进行层次遍历，等遍历到最后一层的时候，返回第一个节点。

bfs

伪代码

层次遍历模板 1：

新建 curLevel 数组保存当前层的节点；
新建 nextLevel 数组保存下一层要遍历的节点；

将 root 加入到 curLevel 中，开始遍历；

重复以下操作：
    遍历 curLevel 中的节点：
        如果该节点存在左子节点，把左子节点加入到 nextLevel 中；
        如果该节点存在右子节点，把右子节点加入到 nextLevel 中；

    判断 nextLevel 中是否有节点：
        如果没有，说明已经遍历到树的最深层次，此时 curLevel 中放的是最深层的所有叶子节点，返回第一个即可；

    让 nextLevel 作为下一个循环中要遍历的对象，即 curLevel = nextLevel；
    将 nextLevel 清空；

层次遍历模板 2：

const queue = [root];

while (queue.length) {
    // 先记录这一层的节点数
    let len = queue.length;

    while (len--) {
        const node = queue.shift();
        node.left && queue.push(node.left);
        node.right && queue.push(node.right);
    }
}

代码(JavaScript/Python/C++)

JavaScript Code

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var findBottomLeftValue = function (root) {
    let curLevel = [root],
        nextLevel = [];

    while (true) {
        for (let node of curLevel) {
            node.left && nextLevel.push(node.left);
            node.right && nextLevel.push(node.right);
        }

        if (!nextLevel.length) return curLevel[0].val;

        curLevel = nextLevel;
        nextLevel = [];
    }
};

Python Code

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def findBottomLeftValue(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        curLevel, nextLevel = [root], []
        while True:
            for node in curLevel:
                if node.left: nextLevel.append(node.left)
                if node.right: nextLevel.append(node.right)
            if not nextLevel: return curLevel[0].val
            curLevel, nextLevel = nextLevel, []

JavaScript Code

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var findBottomLeftValue = function (root) {
    if (!root) return 0;

    const queue = [root];
    let bottomLeft = null;
    while (queue.length) {
        let len = queue.length;

        // 每遍历一层就更新一次最左节点
        // 最后一层更新就是最后一层的的最左节点
        bottomLeft = queue[0];

        while (len--) {
            const node = queue.shift();
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
    }
    return bottomLeft.val;
};

C++ Code

/**
 * 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 findBottomLeftValue(TreeNode* root) {
        TreeNode* bottom_left = nullptr;
        queue<TreeNode*> level;
        level.push(root);

        while (!level.empty()) {
            int size = level.size();
            bottom_left = level.front();

            while (size--) {
                TreeNode* node = level.front();
                level.pop();
                if (node->left) level.push(node->left);
                if (node->right) level.push(node->right);
            }
        }

        return bottom_left->val;

    }
};

复杂度分析

• 时间复杂度：$O(N)$，其中 N 为节点数。

• 空间复杂度: $O(q)$，q 为队列长度。最坏情况是满二叉树，此时 q 为 $2/N$，即为 $O(N)$，N 为二叉树节点数。

方法 2：DFS

思路

想一下递归的路线，如果我们先递归遍历左子树再遍历右子树，那么每遍历到新一层的时候，都是先访问最左边的节点。

• 所以我们只需要在遍历到新一层的时候，记录第一个节点。

• 用 depth 来记录当前层次，用 maxDepth 来记录已经遍历过的最深层次，当 depth > maxDepth 的时候，说明遍历到了新层次：

  • 记录第一个节点的值

  • 更新 maxDepth

伪代码

创建 ans 来记录遍历中遇到的最左边的子节点
创建 maxDepth 来记录已经遍历到的最深层次

定义一个 dfs 函数来遍历二叉树，函数接收 (node, depth) 两个参数，node 是当前遍历到的节点，depth 是当前遍历深度：
    如果 node 为 null，终止遍历

    // 因为我们是先遍历左子节点，再遍历右子节点
    // 所以第一次 depth > maxDepth 的时候，遍历到的就是 depth 这一层最左边的子节点
    // 接着我们更新 maxDepth，之后遍历同一 depth 的节点时，ans 都不会更新了
    如果当前层级 depth > maxDepth：
        更新 ans 为 node.val
        更新 maxDepth 为 depth

    // 分别递归遍历左右子树
    dfs(node.left, depth + 1)
    dfs(node.right, depth + 1)

调用 dfs 函数，传入 (root, 0)
返回 ans

复杂度分析

• 时间复杂度：$O(N)$，其中 N 为节点数。

• 空间复杂度：$O(h)$，其中 $h$ 为树的深度，最坏的情况 $h$ 等于 $N$，其中 N 为节点数，此时树退化到链表。

代码(JavaScript/Python/C++)

JavaScript Code

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var findBottomLeftValue = function (root) {
    let maxDepth = 0;
    let ans = 0;
    helper(root, 1);
    return ans;

    // ******************************

    function helper(root, depth) {
        if (!root) return 0;

        if (depth > maxDepth) {
            maxDepth = depth;
            ans = root.val;
        }

        helper(root.left, depth + 1);
        helper(root.right, depth + 1);
    }
};

Python Code

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    _ans = 0
    _maxDepth = 0

    def helper(self, root, depth):
        if root is None: return 0

        if depth > self._maxDepth:
            self._maxDepth = depth
            self._ans = root.val

        self.helper(root.left, depth + 1)
        self.helper(root.right, depth + 1)

    def findBottomLeftValue(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.helper(root, 1)
        return self._ans

C++ Code

/**
 * 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 findBottomLeftValue(TreeNode* root) {
        findBottomLeftValue(root, 1);
        return ans_;
    }
    void findBottomLeftValue(TreeNode* root, int depth) {
        if (depth > max_depth_) {
            max_depth_ = depth;
            ans_ = root->val;
        }

        if (root->left) findBottomLeftValue(root->left, depth + 1);
        if (root->right) findBottomLeftValue(root->right, depth + 1);
    }
private:
    int max_depth_ = 0;
    int ans_;
};

更多题解可以访问：https://github.com/suukii/91-days-algorithm