面试题6:输入某二叉树的谦虚遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复数字。例如:输入的前序遍历序列{1,2,4,7,3,5,6,8},和中序遍历序列{4,7,2,1,5,3,8,6}。重建二叉树。
测试用例:
- 普通二叉树(完全二叉树、不完全二叉树)
- 特殊二叉树(所有节点都没有右子节点的二叉树、所有节点都没有左子节点的二叉树)
- 特殊二叉树测试(二叉树的根节点指针为NULL、输入的前序遍历序列和中序遍历序列不匹配)
var preOrder = [1,2,4,7,3,5,6,8]; var inOrder = [4,7,2,1,5,3,8,6]; structCore(preOrder,inOrder); function structCore(preOrder,inOrder){ if(preOrder == null || inOrder == null || inOrder.length == 0 ||preOrder.length != inOrder.length){ return null; } var root = { value:null, left:null, right:null }; root.value = preOrder[0]; if(root.value == null){ return; } var index = inOrder.indexOf(root.value); var leftInOrder = inOrder.slice(0,index); var rightInOrder = inOrder.slice(index+1); var leftPreOrder = preOrder.slice(1,leftInOrder.length+1); var rightPreOrder = preOrder.slice(leftInOrder.length+1); for(var i=0;i<leftInOrder.length;i++){ if(leftPreOrder.indexOf(leftInOrder[i]) == -1){ console.log("preOrder dose not match inOrder"); return; } } for(var j=0;j<rightInOrder.length;j++){ if(rightPreOrder.indexOf(rightInOrder[j]) == -1){ console.log("preOrder dose not match inOrder"); return; } } root.left = leftPreOrder[0]; root.right = rightPreOrder[0]; console.log(root); if(leftPreOrder.length>0 && root.value!=null){ structCore(leftPreOrder,leftInOrder); } if(rightPreOrder.length>0 && root.value!=null){ structCore(rightPreOrder,rightInOrder); } }
另外:只有左子节点的二叉树的前序遍历序列和中序遍历序列是相反的。
只有右子节点的二叉树的前序遍历序列和中序遍历序列是相同的。