一、实现二叉树先序，中序和后序遍历

解法一:递归

「二叉树的先序遍历」的思路是：先访问根结点，再访问左子树，最后访问右子树；

「二叉树的中序遍历」的思路是：先访问左子树，再访问根结点，最后访问右子树；

「二叉树的后序遍历」的思路是：先访问左子树，再访问右子树，最后访问根结点

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     *
     * @param root TreeNode类 the root of binary tree
     * @return int整型vector>
     */
    vector<vector<int> > res;
    vector<int> preorder, inorder, postorder;
    vector<vector<int> > threeOrders(TreeNode* root) {
        preOrder(root);
        inOrder(root);
        postOrder(root);
        res.push_back(preorder);
        res.push_back(inorder);
        res.push_back(postorder);
        return res;
    }
    void preOrder(TreeNode* root) {
        if (!root) return;
        preorder.push_back(root->val); // 访问根结点
        preOrder(root->left); // 访问左子树
        preOrder(root->right); // 访问右子树
    }
    void inOrder(TreeNode* root) {
        if (!root) return;
        inOrder(root->left); // 访问左子树
        inorder.push_back(root->val); // 访问根结点
        inOrder(root->right); // 访问右子树
    }
    void postOrder(TreeNode* root) {
        if (!root) return;
        postOrder(root->left); // 访问左子树
        postOrder(root->right); // 访问右子树
        postorder.push_back(root->val); // 访问根结点
    }
};
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

时间复杂度为O(n):遍历二叉树的所有结点
空间复杂度为O(n):递归栈最大为n

解法二:非递归(迭代)

迭代法，就是显式的将该栈模拟出来。
递归的本质就是隐式的维护一个栈。
这里，二者是一个显隐关系。

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 the root of binary tree
     * @return int整型vector>
     */
    vector<vector<int> > res; 
    vector<int> preorder, inorder, postorder; 
    vector<vector<int> > threeOrders(TreeNode* root) {
        preOrder(root); 
        inOrder(root); 
        postOrder(root); 
        res.push_back(preorder); 
        res.push_back(inorder); 
        res.push_back(postorder); 
        return res; 
    }
    void preOrder(TreeNode* root) {
        if (!root) return; 
        stack<TreeNode*> s; 
        TreeNode* p = root; 
        s.push(p); 
        while (s.size()) {
            p = s.top(); // 访问根结点
            s.pop(); // 根结点出栈
            preorder.push_back(p->val); 
            if (p->right) s.push(p->right); // 右子树入栈
            if (p->left) s.push(p->left); // 左子树入栈
        }
        return; 
    }
    void inOrder(TreeNode* root) {
        if (!root) return; 
        stack<TreeNode*> s; 
        TreeNode* p = root; 
        while (s.size() || p) {
            while (p) { // 寻找最左的孩子
                s.push(p); 
                p = p->left; 
            }
            p = s.top(); 
            inorder.push_back(p->val); // 访问
            s.pop(); 
            p = p->right; // 右子树
        }
        return; 
    }
    void postOrder(TreeNode* root) {
        if (!root) return; 
        stack<TreeNode*> s; 
        TreeNode* p = root, *last = NULL; // last记录先前被访问的结点
        while (s.size() || p) {
            while (p) { // 最左的孩子
                s.push(p); 
                p = p->left; 
            }
            p = s.top(); 
            if (!p->right || last == p->right) { // 若该结点没有右孩子，或上一次访问的是右子树，则直接访问该结点
                s.pop(); 
                postorder.push_back(p->val); 
                last = p; // 更新last
                p = NULL; // p置空，防止下一次循环重复访问
            } else {
                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
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

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

二、从中序与后序遍历序列构造二叉树

解法:加粗样式

• 中序遍历顺序:左根右；后序遍历顺序：左右根；根据给出的后序遍历数组可知，数组末元素为根结点值；取出该结点，作为根结点的值。

• 根据中序遍历顺序，找出根结点位置rootIdx；在中序遍历数组中，该结点左边元素为左子树结点值，右边为右子树结点值；在后序遍历数组中，可知从0到rootIdx为左子树结点，从rootIdx到倒数第二个元素为右子数结点。

• 根据中序遍历左子数，后序遍历左子数数组初始化左子树，作为根结点的左子树；根据中序遍历右子数，后序遍历右子数数组初始化右子树，作为根结点的右子树；

• 返回根结点

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
    int post_idx;
    unordered_map<int, int> idx_map;
public:
    TreeNode* helper(int in_left, int in_right, vector<int>& inorder, vector<int>& postorder){
        // 如果这里没有节点构造二叉树了，就结束
        if (in_left > in_right) {
            return nullptr;
        }

        // 选择 post_idx 位置的元素作为当前子树根节点
        int root_val = postorder[post_idx];
        TreeNode* root = new TreeNode(root_val);

        // 根据 root 所在位置分成左右两棵子树
        int index = idx_map[root_val];

        // 下标减一
        post_idx--;
        // 构造右子树
        root->right = helper(index + 1, in_right, inorder, postorder);
        // 构造左子树
        root->left = helper(in_left, index - 1, inorder, postorder);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        // 从后序遍历的最后一个元素开始
        post_idx = (int)postorder.size() - 1;

        // 建立（元素，下标）键值对的哈希表
        int idx = 0;
        for (auto& val : inorder) {
            idx_map[val] = idx++;
        }
        return helper(0, (int)inorder.size() - 1, inorder, postorder);
    }
};


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