发表更新20 分钟读完 (大约2945个字)0次访问

代码随想录算法训练营第15天 | 二叉树层序遍历, 226.翻转二叉树, 101.对称二叉树

二叉树层序遍历

二叉树的层序遍历可以通过队列来完成, 要点在于访问一个节点时, 将其左右孩子指针送入队列中.

最基础的层序遍历:

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
/**
 * 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<int> levelOrder(TreeNode* root) {
        vector<int> result;
        if (!root) return result;
        queue<TreeNode*> que;
        que.push(root);
        while (!que.empty()) {
            TreeNode *node = que.front();
            result.push_back(node -> val);
            que.pop();
            if (node -> left) que.push(node -> left);
            if (node -> right) que.push(node -> right);
        }
        return result;
    }
};

就真的只是能得到层序遍历的顺序而已.

如果要在遍历的每层节点处, 分层进行一些操作, 就需要在遍历的时候, 多出一些对于队列的判定.

有明显层次的层序遍历:

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>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (!root) return result;
        queue<TreeNode*> que;
        que.push(root);
        while (!que.empty()) {
            vector<int> vec;
            int qsize = que.size();             // 当前队列的大小即为要遍历的下一层的节点数
            for (int i = 0; i < qsize; i++) {   // 只遍历这一层, 下一层在下一次while循环内进行遍历
                TreeNode *node = que.front();
                vec.push_back(node -> val);
                que.pop();
                if (node -> left) que.push(node -> left);
                if (node -> right) que.push(node -> right);
            }
            result.push_back(vec);
        }
        return result;
    }
};

在带有层次的层序遍历的代码的基础上, 可以写出很多题目的答案.

如:

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>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (!root) return result;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()) {
            vector<int> vec;
            int qsize = que.size();
            for (int i = 0; i < qsize; i++) {
                TreeNode *node = que.front();
                vec.push_back(node -> val);
                que.pop();
                if (node -> left) que.push(node -> left);
                if (node -> right) que.push(node -> right);
            }
            result.push_back(vec);
        }
        return result;
    }
};

107. 二叉树的层序遍历 II

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 {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> result;
        if (!root)  return result;
        queue<TreeNode *> que;
        que.push(root);
        while (!que.empty()) {
            int qsize = que.size();
            vector<int> levelResult;
            for (int i = 0; i < qsize; i++) {
                TreeNode *node = que.front();
                que.pop();
                levelResult.push_back(node -> val);
                if (node -> left) que.push(node -> left);
                if (node -> right) que.push(node -> right);
            }
            result.push_back(levelResult);
        }
        reverse(result.begin(), result.end());  // 层序遍历,再把层次逆转一下
        return result;
    }
};

199. 二叉树的右视图

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.
 * 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<int> rightSideView(TreeNode* root) {
        vector<int> result;
        if (!root) return result;
        queue<TreeNode *> que;
        que.push(root);
        while (!que.empty()) {                  // 层序遍历, 但只记录每层最后一个节点
            TreeNode *node = que.back();
            result.push_back(node -> val);
            int qsize = que.size();
            for (int i = 0; i < qsize; i++) {
                TreeNode *node = que.front();
                que.pop();
                if (node -> left) que.push(node -> left);
                if (node -> right) que.push(node -> right);
            }
        }
        return result;
    }
};

637. 二叉树的层平均值

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 {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> result;
        if (!root) return result;
        queue<TreeNode *> que;
        que.push(root);
        while (!que.empty()) {                  // 层序遍历, 每层节点求和并求平均
            int qsize = que.size();
            double sum = 0;
            for (int i = 0; i < qsize; i++) {
                TreeNode *node = que.front();
                que.pop();
                sum += node -> val;
                if (node -> left) que.push(node -> left);
                if (node -> right) que.push(node -> right);
            }
            sum /= qsize;
            result.push_back(sum);
        }
        return result;
    }
};

429. 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
/*
// 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>> result;
        if (!root) return result;
        queue<Node *> que;
        que.push(root);
        while (!que.empty()) {
            int qsize = que.size();
            vector<int> levelResult;
            for (int i = 0; i < qsize; i++) {
                Node *node = que.front();
                que.pop();
                levelResult.push_back(node -> val); // 就是对左右节点的判断, 变成了对于一个指针数组的遍历判断
                for (Node *n : node -> children) {
                    if (n) que.push(n);
                }
            }
            result.push_back(levelResult);
        }
        return result;
    }
};

515. 在每个树行中找最大值

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<int> largestValues(TreeNode* root) {
        vector<int> result;
        if (!root) return result;
        queue<TreeNode *> que;
        que.push(root);
        while (!que.empty()) {
            int qsize = que.size();
            int max = INT_MIN;          // 每层记录一个最大值
            for (int i = 0; i < qsize; i++) {
                TreeNode *node = que.front();
                que.pop();
                if (node -> val > max) max = node -> val;
                if (node -> left) que.push(node -> left);
                if (node -> right) que.push(node -> right);
            }
            result.push_back(max);
        }
        return result;
    }
};

116. 填充每个节点的下一个右侧节点指针

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
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;
    Node() : val(0), left(NULL), right(NULL), next(NULL) {}
    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/
class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return root;
        queue<Node *> que;
        que.push(root);
        while (!que.empty()) {          // 层序遍历, 按照先后加next指针
            int qsize = que.size();
            if (qsize == 1) {
                que.front() -> next = NULL;
                if (que.front() -> left) que.push(que.front() -> left);
                if (que.front() -> right) que.push(que.front() -> right);
                que.pop();
            }
            for (int i = 1; i < qsize; i++) {
                Node *first = que.front();
                que.pop();
                Node *second = que.front();
                first -> next = second;
                if (first -> left) que.push(first -> left);
                if (first -> right) que.push(first -> right);
                if (i == qsize - 1) {
                    que.pop();
                    if (second -> left) que.push(second -> left);
                    if (second -> right) que.push(second -> right);
                    second -> next == NULL;
                }
            }
        }
        return root;
    }
};

117. 填充每个节点的下一个右侧节点指针 II

好像和上面那题代码没差.

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
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;
    Node() : val(0), left(NULL), right(NULL), next(NULL) {}
    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/
class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return root;
        queue<Node *> que;
        que.push(root);
        while (!que.empty()) {
            int qsize = que.size();
            if (qsize == 1) {
                que.front() -> next = NULL;
                if (que.front() -> left) que.push(que.front() -> left);
                if (que.front() -> right) que.push(que.front() -> right);
                que.pop();
            }
            for (int i = 1; i < qsize; i++) {
                Node *first = que.front();
                que.pop();
                Node *second = que.front();
                first -> next = second;
                if (first -> left) que.push(first -> left);
                if (first -> right) que.push(first -> right);
                if (i == qsize - 1) {
                    que.pop();
                    if (second -> left) que.push(second -> left);
                    if (second -> right) que.push(second -> right);
                    second -> next == NULL;
                }
            }
        }
        return root;
    }
};

104. 二叉树的最大深度

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
/**
 * 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 maxDepth(TreeNode* root) {
        if (!root) return 0;
        int depth = 0;
        queue<TreeNode *> que;
        que.push(root);
        while (!que.empty()) {              // 就层序遍历的时候加个数数数数
            int qsize = que.size();
            depth++;
            for (int i = 0; i < qsize; i++) {
                TreeNode *node = que.front();
                que.pop();
                if (node -> left) que.push(node -> left);
                if (node -> right) que.push(node -> right);
            }
        }
        return depth;
    }
};

111. 二叉树的最小深度

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.
 * 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) return 0;
        queue<TreeNode *> que;
        que.push(root);
        int level = 0;
        while (!que.empty()) {
            level++;
            int qsize = que.size();
            for (int i = 0; i < qsize; i++) {
                TreeNode *node = que.front();
                que.pop();
                if (!(node -> left) && !(node -> right)) return level;      // 遇见没有左右孩子的节点就返回当前是几层
                if (node -> left) que.push(node -> left);
                if (node -> right) que.push(node -> right);
            }
        }
        return level;
    }
};

做复制完上面这些题之后, 力扣已做题目瞬间+10.

226.翻转二叉树

代码随想录链接

题目

把整个二叉树翻转一下.

自己的想法

可以递归, 可以迭代(层序, 前序(某种意义上的))来完成.

题解一

递归:

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
/**
 * 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 {
private:
    void invert(TreeNode *root) {
        if (!root) return;                  // 空节点就什么也不做
        swap(root -> left, root -> right);  // 交换节点的左右孩子
        invert(root -> left);               // 对左孩子进行相同操作
        invert(root -> right);              // 对右孩子进行相同操作
    }
public:
    TreeNode* invertTree(TreeNode* root) {
        invert(root);
        return 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
25
26
27
28
29
30
31
32
33
34
35
/**
 * 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:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return root;
        stack<TreeNode *> stack;
        stack.push(root);
        while (!stack.empty()) {            // 使用了昨天提到的统一风格的迭代遍历实现
            TreeNode *node = stack.top();
            if (node) {
                stack.pop();
                if (node -> right) stack.push(node -> right);
                if (node -> left) stack.push(node -> left);
                stack.push(node);
                stack.push(NULL);
            } else {
                stack.pop();
                node = stack.top();
                stack.pop();
                swap(node -> left, node -> right);  // 交换左右孩子
            }
        }
        return 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
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 {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return root;
        queue<TreeNode *> que;
        que.push(root);
        while (!que.empty()) {
            int qsize = que.size();
            for (int i = 0; i < qsize; i++) {
                TreeNode *node = que.front();
                que.pop();
                swap(node -> left, node -> right);
                if (node -> left) que.push(node -> left);
                if (node -> right) que.push(node -> right);
            }
        }
        return root;
    }
};

101.对称二叉树

代码随想录链接

题目

判断整个二叉树是否是左右对称的.

自己的想法

先想到的是递归法, 先检查左右孩子是否相同, 再递归地去检查左右孩子起始的子树是否和镜面对应的子树相同

题解一

递归法:

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.
 * 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 {
private:
    bool compare(TreeNode *left, TreeNode *right) {
        if (!left && !right) return true;
        if (!left || !right || (left -> val != right -> val)) return false; // 如果左右孩子不同, 则不满足条件
        return compare(left -> left, right -> right) && compare(left -> right, right -> left);  // 递归地检查子树.
    }
public:
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        return compare(root -> left, root -> right);
    }
};

题解二

使用队列来记录下次要对比的子树的根:

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
/**
 * 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 isSymmetric(TreeNode* root) {
        if (!root) return true;
        queue<TreeNode *> que;
        que.push(root -> left);
        que.push(root -> right);
        while (!que.empty()) {
            TreeNode *left = que.front();       // 相邻的两个节点是要对比的对象
            que.pop();
            TreeNode *right = que.front();
            que.pop();

            if (!left && !right) continue;

            if (!left || !right || (left -> val != right -> val)) return false;
            que.push(left -> left);             // 左孩子的左子树和右孩子的右子树要对比, 一起放入队列
            que.push(right -> right);
            que.push(left -> right);            // 左孩子的右子树和右孩子的左子树需要对比, 一起放入队列
            que.push(right -> left);
        }
        return true;
    }
};

题解三

相似地, 使用栈来记录下次要对比的字数的根节点:

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
/**
 * 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 isSymmetric(TreeNode* root) {
        if (!root) return true;
        queue<TreeNode *> que;
        que.push(root -> left);
        que.push(root -> right);
        while (!que.empty()) {
            TreeNode *left = que.front();       // 同样是取两个节点对比
            que.pop();
            TreeNode *right = que.front();
            que.pop();

            if (!left && !right) continue;

            if (!left || !right || (left -> val != right -> val)) return false;
            que.push(left -> left);             // 同样地将要对比的节点压入栈中
            que.push(right -> right);
            que.push(left -> right);
            que.push(right -> left);
        }
        return true;
    }
};

代码随想录算法训练营第15天 | 二叉树层序遍历, 226.翻转二叉树, 101.对称二叉树

http://wwg.xyz/algorithm-train-day15/

作者

Giles

发布于

2023-03-01

更新于

2023-03-13

许可协议

#

喜欢这篇文章？打赏一下作者吧

评论

目录

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×

×