前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >[每日一题]寻找树中最左下方节点的值

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

作者头像
呼延十
发布2019-07-01 16:45:33
1.5K0
发布2019-07-01 16:45:33
举报
文章被收录于专栏:呼延

来源

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

描述

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

样例

代码语言:javascript
复制
输入:[2,1,3]
输出:1
代码语言:javascript
复制
输人:[1,2,3,4,5,6,#,#,7]
输出:7

解题思路

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

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

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

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

实现代码

代码语言:javascript
复制
/**
 * 寻找树中最左下角的值
 * @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


本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 来源
  • 描述
  • 样例
  • 解题思路
  • 实现代码
    • ChangeLog
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档