汇芳书院

专注计算机视觉、机器学习、分布式计算等领域, 兼聊投资、写作、生活

0%

二叉树的层序遍历(系列)

发表于 更新于 分类于 Valine：
本文字数： 15k 阅读时长 ≈ 14 分钟

102. 二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

 

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：

输入：root = [1]
输出：[[1]]
示例 3：

输入：root = []
输出：[]  

递归的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        result = []
        if not root:
            return result
        self.helper(root, 0, result)
        return result

    def helper(self, root, level, result):
        if len(result) == level:
            result.append([])
        result[level].append(root.val)
        if root.left:
            self.helper(root.left, level+1, result)
        if root.right:
            self.helper(root.right, level+1, result)

使用dummy标记进行迭代

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        result = []
        if not root:
            return result
        dummy = TreeNode()
        p = root
        queue = [root, dummy]
        level = []
        while queue:
            # print("queue,p", [e.val for e in queue],p.val)
            p = queue.pop(0)
            if p != dummy:
                level.append(p.val)
                if p.left:
                    queue.append(p.left)
                if p.right:
                    queue.append(p.right)
            else:
                result.append(list(level))
                level = []
                # 若队列中已无数据，则不再添加标记节点
                if queue:
                    queue.append(dummy)
        return result

迭代：每次直接遍历一层的数据

我们可以用一种巧妙的方法修改广度优先搜索：
首先根元素入队
当队列不为空的时候:
求当前队列的长度Si
依次从队列中取 Si个元素进行拓展，然后进入下一次迭代

它和普通广度优先搜索的区别在于，普通广度优先搜索每次只取一个元素拓展，而这里每次取 Si个元素。

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        result = []
        if not root:
            return result
        p = root
        queue = [root]
        while queue:
            levelQueue = []
            level = len(queue)
            # print("queue, level", [e.val for e in queue], level)
            for i in range(level):
                p = queue.pop(0)
                levelQueue.append(p.val)
                if p.left:
                    queue.append(p.left)
                if p.right:
                    queue.append(p.right)
            result.append(list(levelQueue))
        return result

C++版本，2022年5月2日重刷

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
/**
 * 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) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if (root == nullptr) {
            return ans;
        }
        queue<TreeNode*> q;
        q.emplace(root);
        while (!q.empty()) {
            vector<int> level;
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front(); q.pop();
                level.emplace_back(node->val);
                if (node->left) q.emplace(node->left);
                if (node->right) q.emplace(node->right);
            }
            ans.emplace_back(level);
        }
        return ans;

    }
};

103. 二叉树的锯齿形层序遍历

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

 

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]
示例 2：

输入：root = [1]
输出：[[1]]
示例 3：

输入：root = []
输出：[]

双端队列-广度优先遍历

如果队列中的数据，从队头到队尾都是顺序存放的，那么：

  • 从队头依次访问队列，就是顺序访问
  • 从队尾依次访问队列，就是逆序访问

时间空间复杂度均为O(N)

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
/**
 * 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) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if (root == nullptr) return ans;
        // 双端队列
        deque<TreeNode*> q;
        q.emplace_back(root);
        bool direction = true;
        while (!q.empty()) {
            int size = q.size();
            vector<int> tmp;
            for (int i = 0; i < size; i++) {
                if(direction){
                    // 从队头依次读取数据，并从左到右加入子节点到队列尾部，【这样子节点从队头到队尾是顺序的】
                    // 从队头顺序读取，相当于顺序读取
                    TreeNode* node = q.front(); 
                    q.pop_front();
                    if (node->left) q.emplace_back(node->left);
                    if (node->right) q.emplace_back(node->right);
                    tmp.emplace_back(node->val);
                }else{
                    // 从队尾依次读取数据，并从右到左加入子节点到队列头部，【这样子节点从队头到队尾是顺序的】
                    // 从队尾顺序读取，相当于反序读取
                    TreeNode* node = q.back(); 
                    q.pop_back();
                    if (node->right) q.emplace_front(node->right);
                    if (node->left) q.emplace_front(node->left);
                    tmp.emplace_back(node->val);
                }
            }
            // 通过direction标记控制读取的顺序
            direction = not direction;
            ans.emplace_back(tmp);
        }
        return ans;
    }
};

107. 二叉树的层序遍历 II

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

 

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]
示例 2：

输入：root = [1]
输出：[[1]]
示例 3：

输入：root = []
输出：[]  

看题解基本都是将102题的答案翻转得到，没有想到更好的办法，暂时重写一遍，就当练习了。

广度优先-队列

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
/**
 * 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) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> ans;
        if (root == nullptr) return ans;
        queue<TreeNode*> q;
        q.emplace(root);
        while (!q.empty()){
            int size = q.size();
            vector<int> tmp;
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();q.pop();
                tmp.emplace_back(node->val);
                if (node->left) q.emplace(node->left);
                if (node->right) q.emplace(node->right);
            }
            ans.emplace_back(tmp);
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

深度优先-递归

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
/**
 * 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) {}
 * };
 */
class Solution {
    void levelOrder(TreeNode* root, int level, vector<vector<int>> &ans) {
        if (root == nullptr) return;
        // 注意初始时ans的大小为0
        if (ans.size() < level) ans.emplace_back(vector<int>());
        ans[level-1].emplace_back(root->val);
        if (root->left) levelOrder(root->left, level+1, ans);
        if (root->right) levelOrder(root->right, level+1, ans);
    }
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> ans;
        if (root == nullptr) return ans;

        levelOrder(root, 1, ans);
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

637. 二叉树的层平均值

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

 

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[3.00000,14.50000,11.00000]
解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
因此返回 [3, 14.5, 11] 。
示例 2:

输入：root = [3,9,20,15,7]
输出：[3.00000,14.50000,11.00000]

还是沿用广度优先和深度优先的思路分别求解

广度优先遍历-队列

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
/**
 * 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) {}
 * };
 */
class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> ans;
        if (root == nullptr) return ans;
        queue<TreeNode*> q;
        q.emplace(root);
        while (!q.empty()){
            int size = q.size();
            // 如果先求和然后算平均值，sum可能会溢出，需要为long int
            // 或者也可以记录当前所有数的平均数和个数,每次更新平均数
            double avg = 0;
            int count = 0;
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                avg = (avg*count+node->val)/(++count);
                if (node->left) q.emplace(node->left);
                if (node->right) q.emplace(node->right);
            }
            ans.emplace_back(avg);
        }
        return ans;
    }
};

深度优先遍历

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
/**
 * 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) {}
 * };
 */
class Solution {
    void dfs(TreeNode* root, int level, vector<double> &avg, vector<int> &count) {
        if (root == nullptr) return;
        if (avg.size() < level) {
            avg.emplace_back(0);
            count.emplace_back(0);
        }
        avg[level-1] = (avg[level-1]*count[level-1]+root->val)/(count[level-1]+1);
        count[level-1] += 1;
        if (root->left) dfs(root->left, level+1, avg, count);
        if (root->right) dfs(root->right, level+1, avg, count);
    }
    
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> ans;
        vector<int> count;
        if (root == nullptr) return ans;
        dfs(root, 1, ans, count);
        return ans;
    }
};

111. 二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

 

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：2
示例 2：

输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

深度优先

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
/**
 * 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) {}
 * };
 */
class Solution {
    void dfs(TreeNode* root, int level, int &ans) {
        if (root == nullptr) return;
        if (!root->left && !root->right) {
            ans = min(ans, level);
            return;
        }
        if (root->left) dfs(root->left, level+1, ans);
        if (root->right) dfs(root->right, level+1, ans);
    }
public:
    int minDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        int ans = INT_MAX;
        dfs(root, 1, ans);
        return ans;
    }
};

广度优先

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
/**
 * 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) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        int ans = 0;
        queue<TreeNode*> q;
        q.emplace(root);
        while(!q.empty()) {
            int size = q.size();
            ans++;
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                // 由于是从上到下分层遍历，所以当某层出现叶子结点时，即为最小深度，即刻返回。
                if (!node->left && !node->right) return ans;
                if (node->left) q.emplace(node->left);
                if (node->right) q.emplace(node->right);
            }
        }
        return ans;
    }
};

429. N 叉树的层序遍历

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

 

示例 1：

输入：root = [1,null,3,2,4,null,5,6]
输出：[[1],[3,2,4],[5,6]]
示例 2：

输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]  

广度优先遍历-队列

多叉树的子节点是一个vector对象

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
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> ans;
        if (root == nullptr) return ans;

        queue<Node*> q;
        q.emplace(root);
        while (!q.empty()) {
            int size = q.size();
            vector<int> tmp;
            for (int i = 0; i < size; i++) {
                Node* node = q.front(); q.pop();
                tmp.emplace_back(node->val);
                for(auto child : node->children) {
                    q.emplace(child);
                }
            }
            ans.emplace_back(tmp);
        }
        return ans;
    }
};

深度优先遍历

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
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    void dfs(Node* root, int level, vector<vector<int>> &ans) {
        if (root == nullptr) return;
        if (ans.size() < level) ans.emplace_back(vector<int>());
        ans[level-1].emplace_back(root->val);
        for (auto child : root->children) {
            dfs(child, level+1, ans);
        }
    }
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> ans;
        if (root == nullptr) return ans;

        dfs(root, 1, ans);
        return ans;
    }
};

993. 二叉树的堂兄弟节点

在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。

如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。

我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。

只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。

 

示例 1：

输入：root = [1,2,3,4], x = 4, y = 3
输出：false
示例 2：

输入：root = [1,2,3,null,4,null,5], x = 5, y = 4
输出：true
示例 3：

输入：root = [1,2,3,null,4], x = 2, y = 3
输出：false

还是二叉树的层序遍历：

  1. 层序遍历二叉树，记录x和y的层数以及父节点，当树遍历完或者x，y均遍历到时，结束遍历
  2. 判断x和y是否是堂兄弟节点

广度优先遍历

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
/**
 * 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) {}
 * };
 */
class Solution {
public:
    bool isCousins(TreeNode* root, int x, int y) {
        if (root == nullptr) return false;

        // 记录x和y的层数以及父节点
        int level = 0, xLevel = 0 , yLevel = 0;
        TreeNode* xFather, *yFather;

        queue<TreeNode*> q, fatherQueue;
        q.emplace(root);
        fatherQueue.emplace(nullptr);
        while (!q.empty()) {
            level++;
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front(); q.pop();
                TreeNode* father = fatherQueue.front(); fatherQueue.pop();
                if (node->val == x) {
                    xLevel = level;
                    xFather = father;
                }
                if (node->val == y) {
                    yLevel = level;
                    yFather = father;
                }
                if (node->left) {
                    q.emplace(node->left);
                    fatherQueue.emplace(node);
                }
                if (node->right) {
                    q.emplace(node->right);
                    fatherQueue.emplace(node);
                }

                if (xLevel != 0 && yLevel != 0) break;
            }
            if (xLevel != 0 && yLevel != 0) break;
        }
        if (xLevel == 0 || yLevel == 0) return false;
        return xLevel == yLevel && xFather != yFather;
    }
};

深度优先遍历

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
/**
 * 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) {}
 * };
 */
class Solution {
    // 记录x和y的层数以及父节点
    int level = 0, xLevel = 0 , yLevel = 0;
    TreeNode* xFather, *yFather;
    void dfs(TreeNode* root, TreeNode* pre, int level, int x, int y) {
        if (root == nullptr) return;
        if (root->val == x) {
            xLevel = level;
            xFather = pre;
        }
        if (root->val == y) {
            yLevel = level;
            yFather = pre;
        }
        if (xLevel != 0 && yLevel != 0) return;
        if (root->left) dfs(root->left, root, level+1, x, y);
        if (root->right) dfs(root->right, root, level+1, x, y);
    }
public:
    bool isCousins(TreeNode* root, int x, int y) {
        if (root == nullptr) return false;

        dfs(root, nullptr, 1, x, y);
        if (xLevel == 0 || yLevel == 0) return false;

        return xLevel == yLevel && xFather != yFather;
    }
};

314. 二叉树的垂直遍历

给定一个二叉树，返回其结点 垂直方向（从上到下，逐列）遍历的值。

如果两个结点在同一行和列，那么顺序则为 从左到右。

输入: [3,9,20,null,null,15,7]

3
/
/
9 20
/
/
15 7

输出:

[
[9],
[3,15],
[20],
[7]
]

思路：以根节点为(0,0)坐标，然后层序遍历。其中需要用一个队列记录每个节点的列。

每一个子节点的列号：

  • 若子节点为左孩子，则列号减1
  • 若子节点为右孩子，则列号加1

具体实现同样可以用BFS或DFS均可。

此题现在需要会员，暂时不给答案。

坚持原创分享，您的支持将鼓励我继续创作

欢迎关注我的其它发布渠道

------------- 本文结束,感谢阅读 如有问题可留言交流 -------------