Title / Description
Code // 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; } };
Author
Highlight as C C++ CSS Clojure Delphi ERb Groovy (beta) HAML HTML JSON Java JavaScript PHP Plain text Python Ruby SQL XML YAML diff code
1.1.2
1.1.2