LeetCode题解（5）：二叉树-遍历

发表于 | 分类于
字数统计: 2k | 阅读时长 ≈ 9

LeetCode 题解（5）：二叉树-遍历

learn from cyc2018 and LeetCode

1
2
3
4
5
6
7
// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

二叉树的遍历方式有：

  • 广度遍历：层次遍历
  • 深度遍历：前序、中序、后序遍历

二叉树的层次遍历 (BFS)

二叉树的层次遍历可以借助队列来实现，由于队列是先进先出的，因此可以

  1. 先让根入队，在根出队的同时，让根的左孩子入队，再让根的右孩子入队，这样左孩子会首先被访问。
  2. 被访问之后，左孩子出队的同时打印左孩子，并让左孩子的孩子入队。
  3. 以此类推，直到队列为空。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution{
public:
    vector<int> levelOrder(TreeNode* root){
        vector<int> ret;
        queue<TreeNode*> q;
        if(root)
            q.push(root);
        while(!q.empty()){
            TreeNode* tmp = q.front();
            ret.push_back(tmp->val);
            q.pop();
            if(tmp->left)
                q.push(tmp->left);
            if(tmp->right)
                q.push(tmp->right);
        }
        return ret;
    }
}

637. Average of Levels in Binary Tree (easy)

问题描述

求二叉树每层结点的平均值。

题解

利用两层循环，使得大循环中每次增加一整层元素，而非单个元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        queue<TreeNode*> q;
        vector<double> res;
        if(root != NULL)
            q.push(root);
        while(!q.empty()){
            int count = q.size();
            double sum = 0.0;
            for(int i = 0; i < count; ++ i){
                TreeNode* tmp = q.front();
                q.pop();
                sum += tmp->val;
                if(tmp->left != NULL)
                    q.push(tmp->left);
                if(tmp->right != NULL)
                    q.push(tmp->right);
            }
            res.push_back(sum / count);
        }
        return res;
    }
};

相关问题

102. Binary Tree Level Order Traversal (medium)

107. Binary Tree Level Order Traversal II (easy)

102. Binary Tree Level Order Traversal (medium)

问题描述

层次遍历二叉树，使得每层元素存在于一个向量中。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(root == NULL) return res;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            vector<int> tmp;
            int count = q.size();
            for(int i = 0; i < count; ++ i){
                TreeNode* t = q.front();
                q.pop();
                tmp.push_back(t->val);
                if(t->left != NULL)
                    q.push(t->left);
                if(t->right != NULL)
                    q.push(t->right);
            }
            res.push_back(tmp);
        }
        return res;
    }
};

相关问题

103. Binary Tree Zigzag Level Order Traversal (medium)

107. Binary Tree Level Order Traversal II (easy)

637. Average of Levels in Binary Tree (easy)

107. Binary Tree Level Order Traversal II (easy)

问题描述

与上题一样，但是结果先输出最底层，后输出顶层。

题解

增加一个 reverse 即可。

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
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> res;
        if(root == NULL) return res;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            vector<int> tmp;
            int count = q.size();
            for(int i = 0; i < count; ++ i){
                TreeNode* t = q.front();
                q.pop();
                tmp.push_back(t->val);
                if(t->left != NULL)
                    q.push(t->left);
                if(t->right != NULL)
                    q.push(t->right);
            }
            res.push_back(tmp);
        }
        reverse(res.begin(),res.end());
        return res;        
    }
};

相关问题

102. Binary Tree Level Order Traversal (medium)

637. Average of Levels in Binary Tree (easy)

513. Find Bottom Left Tree Value (medium)

问题描述

寻找二叉树最底层最左边元素的值。

题解

与 102. Binary Tree Level Order Traversal (medium) 一样，输出结果中的最后一列首位即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        if(root == NULL) return -1;
        queue<TreeNode*> q;
        q.push(root);
        vector<int> res;
        while(!q.empty()){
            int count = q.size();
            for(int i = 0; i < count; ++ i){
                TreeNode* t = q.front();
                q.pop();
                if(i == 0)
                    res.push_back(t->val);
                if(t->left != NULL)
                    q.push(t->left);
                if(t->right != NULL)
                    q.push(t->right);
            }
        }
        return res[res.size()-1];        
    }
};

二叉树的深度优先遍历 (DFS)

二叉树的深度优先遍历分为：前序遍历、中序遍历、后序遍历

其递归实现非常简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 前序遍历
void dfs1(TreeNode* root){
    visit(root);
    dfs1(root->left);
    dfs1(root->right);
}

// 中序遍历
void dfs2(TreeNode* root){
    dfs2(root->left);
    visit(root);
    dfs2(root->right);
}

// 后序遍历
void dfs3(TreeNode* root){
    dfs3(root->left);
    dfs3(root->right);
    visit(root);
}

而二叉树深度优先遍历的非递归形式需要用到栈，利用栈先进后出的特性，先将根节点入栈，栈不为空时 pop ，然后将右子树入栈，再将左子树入栈，下面将分别实现三种二叉树深度优先遍历的非递归形式。

144. Binary Tree Preorder Traversal (medium)

问题描述

实现二叉树前序遍历的非递归版本。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if(root == NULL) return res;
        stack<TreeNode*> s;
        s.push(root);
        while(!s.empty()){
            TreeNode* tmp = s.top();
            s.pop();
            res.push_back(tmp->val);
            if(tmp->right != NULL)
                s.push(tmp->right);
            if(tmp->left != NULL)
                s.push(tmp->left);
        }
        return res;
    }
};

94. Binary Tree Inorder Traversal (medium)

问题描述

二叉树中序遍历的非递归版本。

题解

参考 博客

对于中序遍历来说，先访问左子树、后根节点、再访问右子树，那么第一个被我们访问的元素，一定是最左边的元素：

1
2
3
4
5
6
TreeNode* p = root;
stack<TreeNode*> s;
while(p != NULL){
    s.push(p);		// 先将路过的根节点存起来。
    p = p->child;	// 找最左边的节点。
}

此时，有如下两种情形：

不管对于哪种情况，找到该元素之后，理所当然应该出栈，并访问该元素。

1
2
3
p = s.top();
s.pop();
res.push_back(p->val);

接下来，对于上图 a 中的情况：接下来我们只需要访问其根节点，那么继续执行：

1
2
3
p = s.top();
s.pop();
res.push_back(p->val);

左孩子和根都访问完后，接着只需要访问其右子树即可。

1
p = p->right;

这样就又会开始新一轮代码，继续执行下去。

而对于上图情况 b。由于没有左孩子，根节点就是中序序列中的第一个，然后就直接进入右子树，开始新一轮代码。

那么，两图的情况，我们可以统一处理为：

1
2
3
4
p = s.top();
s.pop();
res.push_back(p->val);
p = p->right;

那么，我们最终的结果就为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        if(root == NULL) return res;
        stack<TreeNode*> s;
        TreeNode* p = root;
        while(!s.empty() || p != NULL){
            while(p != NULL){
                s.push(p);
                p = p->left;
            }
            if(!s.empty()){
                p = s.top();
                s.pop();
                res.push_back(p->val);
                p = p->right;
            }
        }
        return res;
    }
};

145. Binary Tree Postorder Traversal (hard)

问题描述

实现后序遍历的非递归版本。

题解

有一种简单的处理技巧：将前序遍历入栈顺序修改为 root, left, right 之后，只需要翻转最终结果即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        if(root == NULL) return res;
        stack<TreeNode*> s;
        s.push(root);
        while(!s.empty()){
            TreeNode* tmp = s.top();
            s.pop();
            res.push_back(tmp->val);
            if(tmp->left != NULL)
                s.push(tmp->left);            
            if(tmp->right != NULL)
                s.push(tmp->right);
        }
        reverse(res.begin(), res.end());
        return res;       
    }
};

显然，我们只是最终的结果和后序遍历的结果一致，但并没有真正意义上实现后序遍历。

参考 博客

后序遍历的难点在于需要判断上次访问的节点位于左子树，还是右子树。如果位于左子树，则需要跳过根节点，先进入右子树，再回头访问根节点；若是位于右子树，则直接访问根节点。

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
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        if(root == NULL) return res;
        stack<TreeNode*> s;
        // pCur: 当前访问节点，pLastVisit：上次访问节点
        TreeNode* pCur = root;
        TreeNode* pLastVisit = NULL;
        // 先将 pCur 移动到左子树最下边
        while(pCur){
            s.push(pCur);
            pCur = pCur->left;
        }
        while(!s.empty()){
            pCur = s.top();
            s.pop();
            // 一个根节点被访问的前提是：无右子树或右子树已被访问过
            if(pCur->right == NULL || pCur->right == pLastVisit){
                res.push_back(pCur->val);
                pLastVisit = pCur;
            }
            else{
                // 根节点再次入栈
                s.push(pCur);
                // 进入右子树，且右子树一定不为空
                pCur = pCur->right;
                while(pCur){
					s.push(pCur);
                    pCur = pCur->left;
                }
            }
        }
        return res;       
    }
};