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)beforefindLeftMostNode(root.left, depth+1);findLeftMostNode(root.right, depth+1);could improve efficiency of recursion.
Always, good luck, Larry!
27 May 2017
