Link to LeetCode Problem

S1: BFS

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

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

https://camo.githubusercontent.com/ff4f16e73968dd0ad7e1ff975d2cb317323510a62724453f264793438d332078/68747470733a2f2f63646e2e6a7364656c6976722e6e65742f67682f7375756b69692f39312d646179732d616c676f726974686d2f6173736574732f3531335f302e706e67

伪代码

层次遍历模板 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);
    }
}

代码

/**
 * 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;

    }
};

/**
 * 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;
};

# 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, []

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

S2: DFS

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