题目描述
给定一个二叉树,在树的最后一行找到最左边的值。
样例
输入:
2
/ \
1 3
输出:
1
输入:
1
/ \
2 3
/ / \
4 5 6
/
7
输出:
7
注意: 您可以假设树(即给定的根节点)不为 NULL。
算法1
dfs
- 1、因为要找左下角的值,因此搜某棵树时,必须先搜它的左子树,再搜它的右子树,这样的搜索顺序就会保证某一层最左边的元素相对同一层来说先被搜到
- 2、
maxh
记录当前最深的深度,搜索过程中,h
遍历标记的是当前节点的深度,若h > maxh
,表示还有更深的深度,更新maxh
和res
时间复杂度 $O(n)$
Java 代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
static int maxh;
static int res;
static void dfs(TreeNode root, int h)
{
if(root == null) return ;
if(h > maxh)
{
res = root.val;
maxh = h;
}
dfs(root.left, h + 1); dfs(root.right, h + 1);
}
public int findBottomLeftValue(TreeNode root) {
maxh = 0;
dfs(root, 1);
return res;
}
}
算法2
bfs
res
记录的是当前枚举到最深层的第一个元素,通过bfs
依次将每一层的元素搜出来,对于每一层的结点来说,若存在左儿子,将左儿子加入队列中,若存在右儿子,将右儿子加入队列中
时间复杂度 $O(n)$
Java 代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
static int res;
static void bfs(TreeNode root)
{
Queue<TreeNode> q = new LinkedList<TreeNode>();
q.add(root);
while(!q.isEmpty())
{
int n = q.size();
res = q.peek().val;
for(int i = 0;i < n;i ++)
{
TreeNode t = q.poll();
if(t.left != null) q.add(t.left);
if(t.right != null) q.add(t.right);
}
}
}
public int findBottomLeftValue(TreeNode root) {
bfs(root);
return res;
}
}