文档章节

513. Find Bottom Left Tree Value

cofama
 cofama
发布于 2017/03/27 12:02
字数 675
阅读 15
收藏 0

原题链接

Given a binary tree, find the leftmost value in the last row of the tree. Note: You may assume the tree (i.e., the given root node) is not NULL.

题目的意思是找到一棵树中最下面的一行的最左边的节点。我用广度优先搜索和深度优先搜索的方法各实现了一遍。

广度优先:广度优先本身就是一层一层的遍历,所以只要记录每层的最左边的节点,那么最终记录的最左节点就是我们要找的。关键问题是如何判断当前节点是否为某一层的最左侧节点。使用C++的queue容器保存节点,访问节点时,依次把它的左、右节点(如果存在的话)压入queue中,然后弹出当前节点。如果能知道何时把某一层的节点全部弹出,那么紧接着要访问的节点就是新的一层最左侧的节点。我用的方法是记录queue的size,这个size是当前层的节点个数,然后依次访问并弹出size个元素,此时queue中的第一个元素便是下一层的最左侧节点,再重新记录queue的size,如此重复下去,直至queue被清空。

class Solution {// 广度优先
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> nodelist;
        int leftmost = root->val;
        nodelist.push(root);
        while(!nodelist.empty()) {
            leftmost = nodelist.front()->val;
            int len = nodelist.size();
            for(int i=0; i<len; i++) {
                TreeNode* cur = nodelist.front();
                nodelist.pop();
                if(cur->left != NULL) nodelist.push(cur->left);
                if(cur->right != NULL) nodelist.push(cur->right);
            }
        }
        return leftmost;
    }
};

深度优先:目标是找到一个最深的节点,遍历时用一个变量depth记录当前访问节点的深度。可能最深的节点会有几个,那么第一个出现的是我们要找的。遍历过程中,用一个变量maxdepth记录最大深度,如果某个节点的depth大于maxdepth,说明它是当前最深的,并且是这个深度第一个出现的节点,那么它成为候选,并且要更新maxdepth;如果depth等于maxdepth,那说明之前已经有一个节点达到了这个深度,并且在当前节点的左侧,所以当前节点不能成为候选。

class Solution {// 深度优先
public:
    int findBottomLeftValue(TreeNode* root) {
        int leftmost = root->val;
        int maxdepth = 0;
        recursiveFind(root, leftmost, 0, maxdepth);
        return leftmost;
    }
    
    void recursiveFind(TreeNode* root, int &leftmost, int depth, int &maxdepth) {
        if(depth>maxdepth) {
            maxdepth = depth;
            leftmost = root->val;
        }
        if(root->left != NULL) recursiveFind(root->left, leftmost, depth+1, maxdepth);
        if(root->right != NULL) recursiveFind(root->right, leftmost, depth+1, maxdepth);
    }
};

另外在discussion上看到一个从右到左的广度优先搜索,逆向思维,这样最后一个访问的节点就直接是答案了,不用再记录每一层有多少个节点。

© 著作权归作者所有

cofama
粉丝 0
博文 24
码字总数 19162
作品 0
广州
程序员
私信 提问
513. Find Bottom Left Tree Value - LeetCode

Question 513. Find Bottom Left Tree Value Solution 题目大意: 给一个二叉树,求最底层,最左侧节点的值 思路: 按层遍历二叉树,每一层第一个被访问的节点就是该层最左侧的节点 Java实现...

yysue
2018/09/02
0
0
Leetcode 513. Find Bottom Left Tree Value

文章作者:Tyan 博客:noahsnail.com | CSDN | 简书 1. Description 2. Solution Iterative Recursive Reference https://leetcode.com/problems/find-bottom-left-tree-value/description/......

SnailTyan
2018/08/07
0
0
二叉查找树 (Binary Search Tree)

今天开始看 数据结构与算法分析C++版本 看到树了 然后写了一下自己的实现, 自己的算法功底太弱了 这对于一个想向底层发展的人来说是难以忍受的,希望 过年之后把这本书看完,加强一下自己的...

ryany
2011/01/27
0
0
二叉树中第二大的值 Second Minimum Node In a Binary Tree

问题: Given a non-empty special binary tree consisting of nodes with the non-negative value, where each node in this tree has exactly or sub-node. If the node has two sub-nodes......

叶枫啦啦
2018/01/12
0
0
在树中第d层,插入v Add One Row to Tree

问题: Given the root of a binary tree, then value and depth , you need to add a row of nodes with value at the given depth . The root node is at depth 1. The adding rule is: gi......

叶枫啦啦
2018/01/12
0
0

没有更多内容

加载失败,请刷新页面

加载更多

强引用、软引用、弱引用、虚引用

强引用: 脱离作用域 或对象被设为空会被回收 内存不足也不会被清理 软引用 脱离作用域 或对象被设为空会被回收 内存不足会被清理 弱引用 下一次GC 会被清理 虚引用 虚引用也称为幻影引用, ...

Java搬砖工程师
13分钟前
0
0
redHat 安装weblogic 未设置 DISPLAY 环境变量 错误

redHat 在安装 weblogic 12的时候,报了一个错误 启动程序日志文件为/tmp/OraInstall2019-05-21_10-34-22AM/launcher2019-05-21_10-34-22AM.log。 正在提取安装程序... . . . . . 完成 检查 ...

internetafei
16分钟前
0
0
Django视图

一个视图函数或者类,简称视图(view),是一个简单的Python 函数(类),它接受Web请求并且返回Web响应。响应可以是HTML页面、一个重定向、一个404错误、一个xml、json数据、或图片等,视图...

彩色泡泡糖
16分钟前
0
0
盘它 | 谁说鱼和熊掌不可兼得?我全部都要!

大家好,我叫王小刚,是一名IT经理 因为各种网络安全政策的强制要求, 我便买了某品牌SSL证书安装在刚部署的网站上 之后再也没在意过它, 随着网站访问量上去了, 网页加载速度延迟问题时常困...

亚洲诚信
17分钟前
0
0
(二) java版电子商务spring cloud分布式微服务b2b2c社交电商-Spring Boot配置文件详解

Spring cloud b2b2c电子商务社交平台源码请加企鹅求求:一零三八七七四六二六。springboot采纳了建立生产就绪Spring应用程序的观点。 Spring Boot优先于配置的惯例,旨在让您尽快启动和运行。...

sccspuercode
19分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部