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

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

因为看了知乎上这篇回答觉得应该做一下搜索，就看了DFS tag下的这道题。

可以先用BFS

这题理解了一下，就是求最后一层的左边第一个结点的value。那么可以用BFS。BFS我已经写烂了。用动态数组保存结果然后读取最后一个item的第一个元素是常规做法，也可以像我这样用O(1) Space保存当前最底层的第一个结点。

    public int findBottomLeftValue(TreeNode root) {
        int res = 0;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int curNum = 1, nexNum = 0, preNum = 0;
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (curNum == preNum) {
                res = node.val;
            }
            curNum--;

            if (node.left != null) {
                q.add(node.left);
                nexNum++;
            }
            if (node.right != null) {
                q.add(node.right);
                nexNum++;
            }

            if (curNum == 0) {
                preNum = nexNum;
                curNum = nexNum;
                nexNum = 0;
            }
        }
        return res;
    }

DFS

DFS我不熟悉，就先写了个保存每层节点，然后取最后一层的第一个node的value的代码，也AC了：

    public int findBottomLeftValue(TreeNode root) {
        int level = 0;
        List<List<TreeNode>> res = new ArrayList<>();
        res = dfs(root, level, res);
        return res.size() > 0 ? res.get(res.size() - 1).get(0).val : -1;
    }

    private List<List<TreeNode>> dfs(TreeNode node, int level, List<List<TreeNode>> res) {
        if (node == null) return null;
        if (level < res.size()) {
            res.get(level).add(node);
        } else {
            List<TreeNode> item = new ArrayList<>();
            item.add(node);
            res.add(item);
        }
        dfs(node.left, level + 1, res);
        dfs(node.right, level + 1, res);
        return res;
    }

然后我优化了一下，用O(1)空间了（我发现用全局变量比较容易思考）：

    int maxLvl = -1, res = 0;

    public int findBottomLeftValue(TreeNode root) {
        int level = 0;
        dfs(root, level);
        return res;
    }

    private void dfs(TreeNode node, int level) {
        if (node == null) return;
        if (level > maxLvl) {
            maxLvl = level;
            res = node.val;
        }
        dfs(node.left, level + 1);
        dfs(node.right, level + 1);
    }

另外，在solutions里看到一种不用global variables的方法：

public class Solution {
    public int findBottomLeftValue(TreeNode root) {
        return findBottomLeftValue(root, 1, new int[]{0,0});
    }
    public int findBottomLeftValue(TreeNode root, int depth, int[] res) {
        if (res[1]<depth) {res[0]=root.val;res[1]=depth;}
        if (root.left!=null) findBottomLeftValue(root.left, depth+1, res);
        if (root.right!=null) findBottomLeftValue(root.right, depth+1, res);
        return res[0];
    }
}

我注意到，那个地址下面很多人都用了一个数组来保存maxDepth和res；想了很久为什么要这样做，直接把这两个int值放在参数里不行吗？试了一下，确实不行，会返回根节点的value。仔细想了一下，似乎是因为res在递归到各个level的时候始终是那一块内存地址，就相当于global variable了！（我甚至回忆起了大一学C语言的时候，余老师在黑板上用方格代表数组的一连串内存地址的场景。。。哈哈哈哈哈），又想到覃超说过的为什么不要归去来兮的原因。恍然大悟了。

很开心。

另外，可以注意一下刚才那个地址里的一个人说的，可以这样写少递归一层：

Add if (null != root.left) and if (null != root.right)before findLeftMostNode(root.left, depth+1);findLeftMostNode(root.right, depth+1);could improve efficiency of recursion.

Always, good luck, Larry!
27 May 2017