首页 > 代码库 > 【LeetCode】Construct Binary Tree from Inorder and Postorder Traversal
【LeetCode】Construct Binary Tree from Inorder and Postorder Traversal
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} };TreeNode *build(vector<int> &inorder, int st_i,int end_i , vector<int> &postorder, int st_p, int end_p){ if (st_i == end_i)//this tree contains only one node { TreeNode *root = new TreeNode(inorder[st_i]); return root; } TreeNode *root = new TreeNode(postorder[end_p]); int left_len = 0; for (int i = st_i; i <= end_i; i++) { if (inorder[i] == postorder[end_p])//find the root node { left_len = i-st_i; break; } } if (left_len > 0)//left subtree exist { root->left = build(inorder, st_i, left_len+st_i-1, postorder, st_p, st_p+left_len-1); } if (st_i+left_len < end_i)//right subtree exist { root->right = build(inorder, st_i+left_len+1, end_i, postorder, st_p+left_len, end_p-1); } return root;}TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder){ if (inorder.size() == 0 || postorder.size() == 0) { return NULL; } TreeNode *root = new TreeNode(postorder.back()); int left_child_length = 0; for (int i = 0; i < inorder.size(); i++) { if (postorder.back() == inorder[i]) { left_child_length = i; break; } } if (left_child_length > 0) { root->left = build(inorder, 0, left_child_length-1, postorder, 0, left_child_length -1); } if (left_child_length < inorder.size()-1) { root->right = build(inorder, left_child_length + 1, inorder.size()-1, postorder, left_child_length, postorder.size()-2); } return root;} };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。