首页 > 代码库 > leetcode 刷题之路 64 Construct Binary Tree from Inorder and Postorder Traversal
leetcode 刷题之路 64 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.
给出二叉树的中序遍历和后序遍历结果,恢复出二叉树。
后序遍历序列的最后一个元素值是二叉树的根节点的值,查找该元素在中序遍历序列中的位置mid,根据中序遍历和后序遍历性质,有:
位置mid以前的序列部分为二叉树根节点左子树中序遍历的结果,得出该序列的长度n,则后序遍历序列前n个元素为二叉树根节点左子树后序遍历的结果,由这两个中序遍历和后序遍历子序列恢复出左子树;
位置mid以后的序列部分为二叉树根节点右子树中序遍历的结果,得出该序列的长度m,则后序遍历序列(除去最后一个元素)后m个元素为二叉树根节点右子树后序遍历的结果,由这两个中序遍历和后序遍历子序列恢复出左子树;
以上描述中递归地引用了由中序遍历和后序遍历恢复子树的部分,因此程序也采用递归实现。
AC code:
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ TreeNode *helper(vector<int> &inorder, int b1, int e1, vector<int> &postorder, int b2, int e2) { if (b1>e1) return NULL; int mid; for (int i = b1; i <= e1; i++) if (inorder[i] == postorder[e2]) { mid = i; break; } TreeNode* root = new TreeNode(inorder[mid]); root->left = helper(inorder, b1, mid - 1, postorder, b2, b2 + mid - b1-1); root->right = helper(inorder, mid + 1, e1, postorder, b2 + mid-b1, e2 - 1); return root; } class Solution { public: TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) { return helper(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1); } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。