Leetcode_14 天数据结构入门_day10

Posted on | Edited on | In ,
| 8.1k | 1:07

3 个题，正好对应二叉树的先、中、后序遍历。

144. Binary Tree Preorder Traversal

Analysis

二叉树的先序遍历，遍历顺序为：根左右。

Code

method 1

递归写法非常简单。

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 {
public:
    void pre(vector<int>& seq, TreeNode *root) {
        if(!root) return;
        seq.push_back(root->val);
        pre(seq, root->left);
        pre(seq, root->right);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ret;
        pre(ret, root);
        return ret;
    }
};

method 2

如果不用递归，也可以使用一个栈来模拟。

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> preorderTraversal(TreeNode* root) {
        vector<int> ret;
        stack<TreeNode*> st;
        while(root || !st.empty()) {
            while(root) {
                st.push(root);
                ret.push_back(root->val);
                root = root->left;
            }
            if(!st.empty()) {
                root = st.top();
                st.pop();
                root = root->right;
            }
        }
        return ret;
    }
};

method 3

实际上还有一种叫做 Morris 遍历的方法，能将空间复杂度降到 $O(1)$。

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> preorderTraversal(TreeNode* root) {
        vector<int> ret;
        if(!root) return ret;
        TreeNode *p1 = root, *p2;
        while(p1) {
            p2 = p1->left;
            if(p2) {
                while(p2->right && p2->right != p1) p2 = p2->right;
                if(!p2->right) {
                    ret.push_back(p1->val);
                    p2->right = p1;
                    p1 = p1->left;
                    continue;
                } else p2->right = nullptr;
            } else ret.push_back(p1->val);
            p1 = p1->right;
        }
        return ret;
    }
};

这种方法很好，但是用的很少（多半是为了面试？）。这种遍历方法实质上只干了一件事情，那就是：利用子树最右子结点的空指针指向其在中序遍历下需要访问的下一个结点，这样就可以不用通过回退来访问下一个结点了，直接用修改好的空指针就可以拿到下一个需要访问的结点的地址，此时，会再次用这个结点进入循环，因为这个子树最右子结点的右指针已经被修改为之前的结点的地址了，所以要再改为 null。

94. Binary Tree Inorder Traversal

Analysis

中序遍历

Code

同样写 3 种遍历方法。

method 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    void inorder(vector<int>& seq, TreeNode* root) {
        if(!root) return;
        inorder(seq, root->left);
        seq.push_back(root->val);
        inorder(seq, root->right);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        inorder(ret, root);
        return ret;
    }
};

method 2

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> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        stack<TreeNode*> st;
        while(root || !st.empty()) {
            while(root) {
                st.push(root);
                root = root->left;
            }
            if(!st.empty()) {
                root = st.top();
                st.pop();
                ret.push_back(root->val);
                root = root->right;
            }
        }
        return ret;
    }
};

method 3

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<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        if(!root) return ret;
        TreeNode *p1 = root, *p2;
        while(p1) {
            p2 = p1->left;
            if(p2) {
                while(p2->right && p2->right != p1) p2 = p2->right;
                if(!p2->right) {
                    p2->right = p1;
                    p1 = p1->left;
                    continue;
                } else {
                    ret.push_back(p1->val);
                    p2->right = nullptr;
                }
            } else ret.push_back(p1->val);
            p1 = p1->right;
        }
        return ret;
    }
};

145. Binary Tree Postorder Traversal

Analysis

后序遍历

Code

method 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    void postorder(vector<int>& seq, TreeNode* root) {
        if(!root) return;
        postorder(seq, root->left);
        postorder(seq, root->right);
        seq.push_back(root->val);
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ret;
        postorder(ret, root);
        return ret;
    }
};

在这几个问题上，递归是真的香...

method 2

使用栈来模拟后序遍历，与前序和中序有一点不同，既可以使用 2 个栈来完成，也可以只用 1 个栈来完成。
双栈：

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<int> postorderTraversal(TreeNode* root) {
        vector<int> ret;
        stack<TreeNode*> st1, st2;
        while(root || !st1.empty()) {
            while(root) {
                st1.push(root);
                st2.push(root);
                root = root->right;
            }
            if(!st1.empty()) {
                root = st1.top();
                st1.pop();
                root = root->left;
            }
        }
        while(!st2.empty()) {
            ret.push_back(st2.top()->val);
            st2.pop();
        }
        return ret;
    }
};

使用双栈的核心思路就是：按照根右左的顺序进行先序遍历，然后用栈弹出这个遍历顺序，这样总体的遍历顺序就是左右根了，这也就是后序遍历的顺序了。实际上，也可以不使用双栈，直接用 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<int> postorderTraversal(TreeNode* root) {
        vector<int> ret;
        stack<TreeNode*> st;
        TreeNode *pre = nullptr;
        while(root || !st.empty()) {
            while(root){
                st.push(root);
                root = root->left;
            }
            root = st.top();
            st.pop();
            if(!root->right || root->right == pre) {
                ret.push_back(root->val);
                pre = root;
                root = nullptr;
            } else {
                st.push(root);
                root = root->right;
            }
        }
        return ret;
    }
};

使用单栈完成模拟后序遍历的思路与先、中序的差别在于：如何判断这个结点已经遇到了 3 次，只有当第 3 次遇到这个结点时，才访问它。所以，要使用一个 pre 指针来记录其右子树是否已经访问（因为开始时就已经将每一层最左边的结点入栈了，所以只用判断右），如果已经访问了右子结点，那么说明这是第 3 次遇到这个结点了，就访问它。

method 3

同样后序遍历也有其对应的 Morris 遍历方法。

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
class Solution {
public:
    void addpath(vector<int>& seq, TreeNode *node) {
        int cnt = 0;
        while(node) {
            cnt++;
            seq.push_back(node->val);
            node = node->right;
        }
        reverse(seq.end() - cnt, seq.end());
    }
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ret;
        if(!root) return ret;
        TreeNode *p1 = root, *p2;
        while(p1) {
            p2 = p1->left;
            if(p2) {
                while(p2->right && p2->right != p1) p2 = p2->right;
                if(!p2->right) {
                    p2->right = p1;
                    p1 = p1->left;
                    continue;
                } else {
                    p2->right = nullptr;
                    addpath(ret, p1->left);
                }
            }
            p1 = p1->right;
        }
        addpath(ret, root);
        return ret;
    }
};

Morris 的后序遍历方法本质上其实与双栈实现的后序遍历没有太大的区别，但是胜在空间复杂度是 $O(1)$。换句话说，addpath 函数在做的事情，就是在回到根结点的时候，利用根节点按照根右的顺序遍历左子树，然后再用 reverse 函数逆置，这样整体顺序就是右根了，而左边的叶子结点一定是排在二者前面的，所注意最终顺序就是左右根了。

Summary

二叉树的遍历的递归做法，其实就是 DFS。尽管递归很简单，但是对非递归的做法也要熟悉，Morris 可能要求较少，但是用单栈实现的非递归做法，多看的话，应该可以很熟练的背下来吧。

Buy me a coffee ? :)
0%