wzwzw

C++ code posted by bbbb
created at 12 Apr 14:51, updated at 22 Apr 20:32

Edit | Back 
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
 

// 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:
    // Construct Binary Tree from Preorder and Inorder Traversal 
    // 由先序和中序重建二叉树
    TreeNode* buildTreeInPre(vector<int>& preorder, vector<int>& inorder) {
            if (preorder.empty())
                return NULL;
            stack<TreeNode *> st;
            int pt = 0, it = 0;
            bool flag = false;
            TreeNode *pnode = new TreeNode(preorder[pt++]), *root = pnode;
            st.push(pnode);
            while (pt < preorder.size() || it < inorder.size()) {
                if (!st.empty() && st.top()->val == inorder[it]) {
                    pnode = st.top(); st.pop(); 
                    it ++;
                    flag = true;
                }
                else {
                    TreeNode* cur = new TreeNode(preorder[pt++]);
                    if (flag) {
                       pnode->right = cur;
                       flag = false;
                    }
                    else {
                        st.top()->left = cur;
                    }
                    st.push(cur);
                }
            }
            return root; 
        }

    // Construct Binary Tree from Inorder and Postorder Traversal
    // 由后序和中序重建二叉树
    TreeNode* buildTreeInPost(vector<int>& inorder, vector<int>& postorder) {
        if (inorder.empty())
            return NULL;
        
        stack<TreeNode *> st;
        int pt = postorder.size() - 1, it = pt;
        TreeNode *pnode = new TreeNode(postorder[pt--]), *root = pnode;
        st.push(pnode);
        bool flag = false;
        while (pt >= 0 || it >= 0) {
            if (!st.empty() && st.top()->val == inorder[it]) {
                pnode = st.top(); st.pop();
                flag = true;
                it --; 
            } 
            else {
                TreeNode* cur = new TreeNode(postorder[pt--]);
                if(flag) {
                    pnode->left = cur;
                    flag = false; 
                } 
                else {
                    st.top()->right = cur;
                }
                st.push(cur);
            }
        }
        return root;
    }
};
2.4 KB in 3 ms with coderay