java 数据结构与算法 刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java /article/details/123063846
先深度优先 遍历左结点,获得可到达的最左结点高度A 然后递归向上继续深度优先 如果递归向上过程,没有
发现比A高的高度,那么最开始的那个左节点就是我们要找的 但如果我们发现
比A高的,那么我们优先进入更高层。而因为我们先深度遍历左节点。所以就算进入更高层,依然是获得当前结点的可到达的最左结点B,然后更新高度为B。继续递归向上。 直到遍历完成,注意只有高度更高时,才更新
java">
class Solution {
int curVal = 0 ;
int curHeight = 0 ;
public int findBottomLeftValue ( TreeNode root) {
dfs ( root, 0 ) ;
return curVal;
}
public void dfs ( TreeNode root, int height) {
if ( root == null ) return ;
height++ ;
dfs ( root. left, height) ;
dfs ( root. right, height) ;
if ( height > curHeight) {
curHeight = height;
curVal = root. val;
}
}
}
2. 广度优先
解题思路:所有结点遍历一遍的情况下,广度优先比深度优先 慢一倍.因为入队列出队列,每个结点访问两次
广度优先,就相当于层级遍历,正好适合这道题 每一层我们从右到左遍历,当遍历到最后一个结点时,正好是最后一层的最左边结点 所以我们要先入队列右节点,然后在入队列左节点,和一般情况下,从左到右层级遍历是反过来的。这点要注意
java">class Solution {
public int findBottomLeftValue ( TreeNode root) {
int ret = 0 ;
Queue < TreeNode > queue = new ArrayDeque < TreeNode > ( ) ;
queue. offer ( root) ;
while ( ! queue. isEmpty ( ) ) {
TreeNode p = queue. poll ( ) ;
if ( p. right != null ) {
queue. offer ( p. right) ;
}
if ( p. left != null ) {
queue. offer ( p. left) ;
}
ret = p. val;
}
return ret;
}
}