根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如,给出
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树:
3
/ \
9 20
/ \
15 7
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
老题目了,已知后序遍历序列和前序遍历序列以后,都能够知道一棵树的根结点位置,前序遍历在序列第一个位置,后序遍历在序列第二个位置。
确定了根结点的位置和值以后,遍历中序遍历,比较中序遍历序列中与根结点值相同的值,就找到根结点在中序遍历的位置,此时中序遍历根结点左边即为左子树,右边即为右子树,递归的去查找左子树和右子树的根节点,并挂到根节点的左右孩子指针上即可。
代码:
class Solution {
public:
/**
根据中序和后序遍历构造二叉树
后序遍历的最后一个节点是树的根节点,根据这个查找到中序遍历的根节点
**/
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
int size = (int)inorder.size();
return getRoot(0, size-1, 0, size-1, inorder, postorder);
}
// 标记当前树在中序和后序的位置
TreeNode* getRoot(int inLeft, int inRight, int postLeft, int postRight,
vector<int>& inorder, vector<int>& postorder){
if (inLeft > inRight) {
return nullptr;
}
int rootVal = postorder[postRight]; // 根节点的值
int k = inLeft; // k指向根节点在中序的位置
for (; k <= inRight; ++k) {// 查找在中序遍历的位置
if (inorder[k] == rootVal) {
break;
}
}
TreeNode* tmp = new TreeNode(rootVal);
int leftTreeNum = k - inLeft;
tmp->left = getRoot(inLeft, k-1, postLeft, postLeft + leftTreeNum-1, inorder, postorder);
tmp->right = getRoot(k+1, inRight, postLeft+leftTreeNum, postRight-1, inorder, postorder);
return tmp;
}
};
Comments | 0 条评论