LeetCode102二叉树层次遍历

Posted on | | Visitors:
Words count in article: 511 字 | Reading time ≈ 3 分

题目链接

https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

题解一：非递归BFS

  • 用队列存储每层的结点
  • 获取到一层结点后，则可以获得该层所有结点的val和下一层的所有结点
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
// Problem: LeetCode 102
// URL: https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
// Tags: Tree BFS DFS Recursion Queue
// Difficulty: Medium

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr){}
};

class Solution{
public:
    vector<vector<int>> levelOrder(TreeNode* root){
        vector<vector<int>> result;  // 最终结果
        queue<TreeNode*> parentNodes;  // 父层结点
        if(root!=nullptr)
            parentNodes.push(root);

        while(!parentNodes.empty()){
            // 找子层结点
            queue<TreeNode*> childNodes; // 子层结点
            vector<int> parentVals;  // 父层结点元素
            while (!parentNodes.empty()){
                root = parentNodes.front();
                parentNodes.pop();
                parentVals.push_back(root->val);
                if (root->left != nullptr)
                    childNodes.push(root->left);
                if (root->right != nullptr)
                    childNodes.push(root->right);
            }
            parentNodes = childNodes;
            result.push_back(parentVals);
        }
        
        return result;
    }
};

int main()
{
    cout << "helloworld" << endl;
    // system("pause");
    return 0;
}

题解二：DFS递归

  • 用变量level记录当前处于哪一层
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
// Problem: LeetCode 102
// URL: https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
// Tags: Tree BFS DFS Recursion Queue
// Difficulty: Medium

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr){}
};

class Solution{
public:
    vector<vector<int>> levelOrder(TreeNode* root){
        vector<vector<int>> result; // 最终结果
        dfs(result, root, 0);
        return result;
    }

    void dfs(vector<vector<int>>& result, TreeNode* root, int level){
        // 空指针，无动作
        if(nullptr==root){
            return;
        }
        // 如果该层第一次被遍历到，则为该层创建空数组
        if(result.size()<=level){
            result.push_back(vector<int>());
        }
        // 遍历该结点
        result[level].push_back(root->val);
        // 遍历左子树
        dfs(result, root->left, level + 1);
        // 遍历右子树
        dfs(result, root->right, level + 1);
    }
};

int main()
{
    cout << "helloworld" << endl;
    // system("pause");
    return 0;
}

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!