513. Find Bottom Left Tree Value

Given a binary tree, find the leftmost value in the last row of the tree.

Example 1:

Input:

    2
   / \
  1   3

Output:
1

Example 2:

Input:

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

Output:
7

Note: You may assume the tree (i.e., the given root node) is not NULL.

記錄res還有該res的深度，然後DFS去找，如果發現當前深度比較深，那就更新res的值。要控制好DFS的順序，要先往左走下去到底。

// Recursion
void helper(TreeNode* node, int depth, int& res, int& maxDepth) {
    if (!node) return;
    helper(node->left, depth + 1, res, maxDepth);
    helper(node->right, depth + 1, res, maxDepth);
    if (depth > maxDepth) {
        res = node->val;
        maxDepth = depth;
    }
}
int findBottomLeftValue(TreeNode* root) { // time: O(n); space: O(h)
    int res = -1, maxDepth = 0;
    helper(root, 1, res, maxDepth);
    return res;
}

用一個queue來幫助實現level order的目標，只是traversal的方向是從每層的右到左，這樣最後結束時，TreeNode*指到的node就是最左下的node。

// BFS Level Order Traversal (From Right to Left)
int findBottomLeftValue(TreeNode* root) { // time: O(n); space: O(n)
    queue<TreeNode*> q({root});
    TreeNode* t = nullptr;
    while (!q.empty()) {
        for (int i = q.size() - 1; i >= 0; --i) {
            t = q.front(); q.pop();
            if (t->right) q.push(t->right);
            if (t->left) q.push(t->left);
        }
    }
    return t->val;
}