[每日一题]寻找树中最左下方节点的值

数据结构和算法►二叉树 , , 评论

来源

lintcode-寻找树中最左下节点的值

描述

给定一棵二叉树，找到这棵树最中最后一行中最左边的值。

样例

1
2
输入:[2,1,3]
输出:1
1
2
输人:[1,2,3,4,5,6,#,#,7]
输出:7

解题思路

首先这道题一看就是层次遍历,这里帮大家回顾下二叉树的层次遍历.二叉树介绍及其前中后遍历实现.

然后这里要求得最左边的值,那么怎么才能知道当前拿到的节点是不是最后一个节点呢?

再想一下,我们平时的层次遍历拿到的是什么样子的呢?

拿到的是从左到右的顺序,那么最后一个节点,就是最右下角的节点,那么,每一层从右向左遍历,最后一个就是最左的节点啦!

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 寻找树中最左下角的值
 * @param root
 * @return
 */
public int findBottomLeftValue(TreeNode root) {
  TreeNode cur = null;
  //队列
  Queue<TreeNode> queue = new LinkedList();
  //根节点入队
  queue.offer(root);
  while(!queue.isEmpty()){
    //出队一个元素
    cur = queue.poll();
    //按顺序入队其右孩子和左孩子
    if(cur.right != null)
      queue.offer(cur.right);  
    if(cur.left != null)
      queue.offer(cur.left);
  }
  //所有元素出队后拿到的就是最后一个节点,返回
  return cur.val;
}

完.





ChangeLog

2018-12-19 完成

以上皆为个人所思所得，如有错误欢迎评论区指正。

欢迎转载，烦请署名并保留原文链接。

联系邮箱：huyanshi2580@gmail.com

更多学习笔记见个人博客——>呼延十

呼延十Developer

个人简介。