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.
因?yàn)榭戳酥跎?a target="_blank" rel="nofollow">這篇回答覺得應(yīng)該做一下搜索吭从，就看了DFS tag下的這道題朝蜘。
可以先用BFS
這題理解了一下，就是求最后一層的左邊第一個(gè)結(jié)點(diǎn)的value涩金。那么可以用BFS谱醇。BFS我已經(jīng)寫爛了。用動(dòng)態(tài)數(shù)組保存結(jié)果然后讀取最后一個(gè)item的第一個(gè)元素是常規(guī)做法步做，也可以像我這樣用O(1) Space保存當(dāng)前最底層的第一個(gè)結(jié)點(diǎn)副渴。
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我不熟悉，就先寫了個(gè)保存每層節(jié)點(diǎn)全度，然后取最后一層的第一個(gè)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;
}
然后我優(yōu)化了一下，用O(1)空間了（我發(fā)現(xiàn)用全局變量比較容易思考）：
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];
}
}
我注意到勉盅，那個(gè)地址下面很多人都用了一個(gè)數(shù)組來(lái)保存maxDepth和res；想了很久為什么要這樣做顶掉，直接把這兩個(gè)int值放在參數(shù)里不行嗎草娜？試了一下，確實(shí)不行痒筒，會(huì)返回根節(jié)點(diǎn)的value宰闰。仔細(xì)想了一下，似乎是因?yàn)閞es在遞歸到各個(gè)level的時(shí)候始終是那一塊內(nèi)存地址簿透，就相當(dāng)于global variable了Ｒ轶 （我甚至回憶起了大一學(xué)C語(yǔ)言的時(shí)候，余老師在黑板上用方格代表數(shù)組的一連串內(nèi)存地址的場(chǎng)景萎战。。舆逃。哈哈哈哈哈）蚂维，又想到覃超說過的為什么不要?dú)w去來(lái)兮的原因÷肥ǎ恍然大悟了虫啥。
很開心。
另外奄妨，可以注意一下剛才那個(gè)地址里的一個(gè)人說的涂籽，可以這樣寫少遞歸一層：
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
