LeetCode 515 Find Largest Value in Each Tree Row

By Jalan

知识工具需求

数据结构和算法

树的层序遍历

题解

第一次

思路

需要统计树的每层的一些信息
采用层序遍历,并且对每层的末尾有个标记.
可以采用递归或非递归.
一般这种有标记的,非递归写起来快一点,而且不需要全局变量.

1. 判断边界条件
2. 遍历树,遍历过程中遇到层结尾标记的时候统计本层信息.
3. 返回
   第一次采用非递归,和第二次只有BFS函数不一样,rowSize 是层结束标记,rowMax是层需要的统计信息.

预期时间复杂度

O(n)

编写用时

2年没写题了,这个居然写了20分钟…

代码

CPP

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
#include <climits>
#include <functional>
#include <iostream>
#include <new>
#include <queue>
#include <type_traits>
#include <vector>
struct TreeNode {
    int       val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val( 0 ), left( nullptr ), right( nullptr ) {}
    TreeNode( int x ) : val( x ), left( nullptr ), right( nullptr ) {}
    TreeNode( int x, TreeNode* left, TreeNode* right ) : val( x ), left( left ), right( right ) {}
};

using namespace std;
class Solution
{
public:
    void BFS( TreeNode* root, vector< int >& answers )
    {
        queue< TreeNode* > q;
        q.push( root );
        int rowSize = 1;
        int rowMax  = INT_MIN;
        while ( !q.empty() ) {
            //出队
            TreeNode* top = q.front();
            if ( top->val > rowMax ) {
                rowMax = top->val;
            }
            rowSize--;
            q.pop();

            //入队
            if ( top->left != nullptr ) {
                q.push( top->left );
            }
            if ( top->right != nullptr ) {
                q.push( top->right );
            }

            if ( rowSize == 0 ) {
                answers.emplace_back( rowMax );
                rowMax  = INT_MIN;
                rowSize = q.size();
            }
        }
    };
    vector< int > largestValues( TreeNode* root )
    {
        //采用队列遍历整个树.answers保存每层的最大值
        vector< int > answers;
        //判空
        if ( root == nullptr ) {
            return answers;
        }
        //遍历
        BFS( root, answers );
        //返回
        return answers;
    }
};
int main( int argc, const char** argv )
{
    Solution  s;
    TreeNode* root     = new TreeNode( 1 );
    root->left         = new TreeNode( 3 );
    root->right        = new TreeNode( 2 );
    root->left->left   = new TreeNode( 5 );
    root->left->right  = new TreeNode( 3 );
    root->right->right = new TreeNode( 9 );
    auto ans           = s.largestValues( root );

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

运行用时

结尾

看在我写了这么多注释的份上可以给我点个赞嘛,求求惹=]砰砰砰,给我加点写下去的油呀
@.@
也欢迎关注我的CSDN账号呀=]

                                        **开心code每一天**
1