给定一颗二叉树的 (【先序遍历】 或者 【后序遍历】)和 【中序遍历】 可以恢复这颗二叉树。
给定一颗二叉搜索树 【先序遍历】 和 【后序遍历】对其进行排序即可得到【中序遍历】,然后再其进行恢复。
但是其实对于二叉搜索树,我们可以简化(【先序遍历】 和 【后序遍历】 => 【中序遍历】)的步骤,例如:在得到后序遍历的结果后,在重建的过程中,因为根节点是最后一个,所以我们右后往前,拿到值的是时候,进行大小的比较,来判断这个点是左节点(小于的)还是右节点(大于的);
参考:449题,leetcode 449
//序列化,生成后序遍历的结果。var serialize = function(root) {const ans = [];const midTravel = (node)=>{if(node ===null) returnmidTravel(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);};
