513 Find Bottom Left Tree Value

513. Find Bottom Left Tree Value

1. Question

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.

2. Implementation

(1) BFS

思路：对树用BFS进行遍历, 将每行中的第一个node的值存入res

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int res = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                TreeNode curNode = queue.remove();

                if (i == 0) {
                   res = curNode.val; 
                }

                if (curNode.left != null) {
                    queue.add(curNode.left);
                }

                if (curNode.right != null) {
                    queue.add(curNode.right);
                }
            }
        }
        return res;
    }
}

(2) DFS

思路，对树用DFS进行遍历，维护一个变量height表示当前所知的最深的深度，另一个depth表示当前遍历的深度，如果depth > height, 说明我们到达新的一层，由于我们是从左到右去DFS，所以这种情况下，得到的node必然是每行中的第一个node，将这个node保存下来

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        int[] height = {-1};
        int[] res = {root.val};

       findBottomLeftValueByDFS(root, 0, height, res);
        return res[0];
    }

    public void findBottomLeftValueByDFS(TreeNode node, int depth, int[] height, int[] res) {
        if (node == null) {
            return;
        }

        if (node.left == null && node.right == null) {
            if (depth > height[0]) {
                res[0] = node.val;
                height[0] = depth;
            }
        }

        findBottomLeftValueByDFS(node.left, depth + 1, height, res);
        findBottomLeftValueByDFS(node.right, depth + 1, height, res);
    }
}

3. Time & Space Complexity

时间复杂度为O(n), n为树的node个数，空间复杂度为O(w), w为树的宽度，即最多node的一个level