给定一颗二叉树的 (【先序遍历】 或者 【后序遍历】)和 【中序遍历】 可以恢复这颗二叉树。
给定一颗二叉搜索树 【先序遍历】 和 【后序遍历】对其进行排序即可得到【中序遍历】,然后再其进行恢复。
但是其实对于二叉搜索树,我们可以简化(【先序遍历】 和 【后序遍历】 => 【中序遍历】)的步骤,例如:在得到后序遍历的结果后,在重建的过程中,因为根节点是最后一个,所以我们右后往前,拿到值的是时候,进行大小的比较,来判断这个点是左节点(小于的)还是右节点(大于的);
参考:449题,leetcode 449
//序列化,生成后序遍历的结果。
var serialize = function(root) {
const ans = [];
const midTravel = (node)=>{
if(node ===null) return
midTravel(node.left);
midTravel(node.right)
ans.push(node.val);
}
midTravel(root);
return ans.join(',')
};
/**
* Decodes your encoded data to tree.
*
* @param {string} data
* @return {TreeNode}
*/
var deserialize = function(data) {
const n = data.length;
if(n===0) return null
// 拿到数组
const stack = data.split(',').map(v => parseInt(v));
const construct =(low,top)=>{
if(stack.length===0 || stack[stack.length-1] <low || stack[stack-1]>top){
return null
}
const val = stack.pop();
const node = new TreeNode(val)
node.right = construct(val,top);
node.left = construct(low,val)
return node
}
return construct(-Number.MAX_SAFE_INTEGER, Number.MAX_SAFE_INTEGER);
};