The Level In Tree

发表于 | 分类于

The Level In Tree(树中按层遍历相关的问题)

题目描述1：

给定一棵树的头结点head，实现按层遍历打印。

解题思路：

按层遍历的思路通常是借助于队列数据结构。我们先将节点入队，出队的时候将该节点的左右节点各自入队，当上一层的节点出队结束后，我们继续将刚刚入队的这一层节点出队，实现了按层遍历。我们可以使用两个队列分别来记录上一层和当前层的节点；也可以只用一个队的方法，每次记录当前入队的最后一个节点，下一层遍历的时候我们就只要出队到该节点即可。

代码如下：

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
class printByLevel1{ //利用两个队的方法
public:
    void printByLevel(treeNode* root){
        queue<treeNode*> q1;
        queue<treeNode*> q2; //定义两个队列
        queue<treeNode*> tmp;
        int level = 1;
        if (root == NULL)
            return;
        q1.push(root);//先将根节点入队
        while(!q1.empty()){
            cout << "Level" << level << ":";
            while(!q1.empty()){
                if (q1.front()->left != NULL){
                    q2.push(q1.front()->left);
                }
                if (q1.front()->right != NULL){
                    q2.push(q1.front()->right);
                }
                cout << q1.front()->val << " ";
                q1.pop();
            }//不断的将当前层的左右节点压入到另外一个队中
            tmp = q2;
            q2 = q1;
            q1 = tmp; //交换当前队和上一层队，对下一层节点遍历
            cout << endl;
        }
    }
};

解法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
lass printByLevel2{
public:
    void printByLevel(treeNode* head){
        queue<treeNode*> q;
        treeNode* flag = head; //保存上一层的最后一个节点
        treeNode* next_flag = NULL; //保存当前层的最后一个节点
        q.push(head);
        while(!q.empty()){
            cout << q.front()->val;
            if (q.front()->left != NULL){
                q.push(q.front()->left);
                next_flag = q.front()->left; 
                //左节点入队，更新最后一个节点
            }
            if (q.front()->right != NULL){
                q.push(q.front()->right);
                next_flag = q.front()->right;
                //右节点入队，更新最后一个节点
            }
            if (q.front() == flag){
                cout << endl;
                flag = next_flag;
                //如果当前是最后一个节点，输出换行符，更新最后一个节点
            }
            q.pop();//出队头节点
        }
    }
};

题目描述2：

自底向上按层遍历树的每一层节点并返回结果。与上面题目类似，具体的题目描述可以看LeetCode107.

代码如下：

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> res;
        if (!root) return res;
        queue<TreeNode*> q1;
        q1.push(root);
        queue<TreeNode*>q2;
        queue<TreeNode*>tmp;
        while(!q1.empty()){
            vector<int> vec;
            while(!q1.empty()){
                vec.push_back(q1.front()->val);
                if (q1.front()->left) q2.push(q1.front()->left);
                if (q1.front()->right) q2.push(q1.front()->right);
                q1.pop();
            }
            res.push_back(vec);
            tmp = q1;
            q1 = q2;
            q2 = tmp;
        }
        reverse(res.begin(), res.end());
        //主要不同之处将遍历的结果逆序后返回即可
        return res;
    }
};

题目描述3：

定义树中的节点增加一个next节点，要求给定一棵树的头结点，要求每层的树的节点的next指针指向其同层右侧的指针。

例子：

详细的描述说明可以看leetcode上题目1，以及题目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
37
38
39
40
41
42
43
/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (!root) return;
        queue<TreeLinkNode*> q1;
        queue<TreeLinkNode*> q2;
        //定义两个队列用于保存上一层和当前层的树的节点
        q1.push(root);
        //先将树的头结点入队
        while(!q1.empty()){
            TreeLinkNode* pre = q1.front();
            q1.pop();
            if (pre->left) q2.push(pre->left);
            if (pre->right) q2.push(pre->right);
            //因为要将树的节点连接所以先将当前层的节点作为pre，剩下不断的往下遍历同层节点即可
            while(!q1.empty()){
                TreeLinkNode* next = q1.front();
                if (next->left) q2.push(next->left);
                if (next->right) q2.push(next->right);
                //每pop一个节点就将其左右节点入队，作为下一层的节点
                pre->next = next;
                //建立新的连接
                pre = next;
                //改变pre指针
                q1.pop();
            }
            pre->next = NULL;
            queue<TreeLinkNode*>tmp = q1;
            q1 = q2;
            q2 = tmp;
            //这步将下一层的数据保存到当前层的队列中，然后将下一层队列置空
        }
        
    }
};

题目描述4

类似用到树的按层遍历的性质的有，给定一棵树的头结点，要求输出从右侧看这棵树，从第一层到最后一层所看见的树的节点。其实这题的主要思路也是类似的，因为我们知道每层的节点后，我们只要将当前层的末尾节点保存到结果中就可以了。所以需要举一反三，利用之前的题目的解法可以很快的解答出。

例子:

这题也是leetcode上的题目，具体的题目描述可以看这边.

代码如下：

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(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        if (!root) return res;
        queue<TreeNode*> q1;
        queue<TreeNode*> q2;
        //同样定义两个队列保存当前层和下一层的节点
        q1.push(root);
        while(!q1.empty()){
            res.push_back(q1.back()->val);
            //直接将当前层的末尾入队，即为最右侧的节点
            while(!q1.empty()){
                TreeNode* front = q1.front();
                if (front->left) q2.push(front->left);
                if (front->right) q2.push(front->right);
                q1.pop();
            }
            queue<TreeNode*> tmp = q1;
            q1 = q2;
            q2 = tmp;
            //更新当前层和下一层的数据
        }
    return res;
    }
};

题目描述5

给定一棵树的头结点，要求返回树的最左侧下方的那个节点。具体的描述可以看LeetCode513.解题思路是按层遍历，找到最后一层的最左侧节点返回即可。

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(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        queue<TreeNode*> cur;
        queue<TreeNode*> next;
        vector<int> res;
        cur.push(root);
        while(!cur.empty()){
            res.push_back(cur.front()->val);
            while(!cur.empty()){
                TreeNode* front = cur.front();
                cur.pop();
                if (front->left) next.push(front->left);
                if (front->right) next.push(front->right);
            }
            queue<TreeNode*> tmp = cur;
            cur = next;
            next = tmp;
        }
        return res[res.size() - 1];
        //保存每一层的最左侧，返回最后一层的那个节点即可。
    }
};

题目描述6

给定一棵树的头结点，要求我们按照Z字型分层打印树的内容。
同样我们可以利用按层遍历树的方式，不同之处是需要加上一个direction标识用于判断当前层是从前往后还是从后往前答应。具体的题目描述可以看LeetCode103。

代码如下：

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;w
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
//按照锯齿状分层遍历树
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if (!root) return res;
        
        deque<TreeNode*> q1;
        deque<TreeNode*> q2;
        deque<TreeNode*> tmp;
        bool direction = true;
        q1.push_back(root);
        while(!q1.empty()){
            vector<int> vec;
            while(!q1.empty() && direction){
                vec.push_back(q1.front()->val);
                if (q1.front()->left){
                    q2.push_front(q1.front()->left);
                }
                if (q1.front()->right){
                    q2.push_front(q1.front()->right);
                }
                q1.pop_front();
            }
            while(!q1.empty() && !direction){
                vec.push_back(q1.front()->val);
                if (q1.front()->right) q2.push_front(q1.front()->right);
                if (q1.front()->left) q2.push_front(q1.front()->left);
                q1.pop_front();
            }
            res.push_back(vec);
            direction = !direction;
            //每次遍历结束后都改变一下遍历的方向即可
            tmp = q1;
            q1 = q2;
            q2 = tmp;
        }
        return res;
        
        
    }
};