在线测评地址:牛客网
题目描述
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
思路
前序遍历: 根左右
中序遍历: 左根右
前序遍历中第一个数为树的根节点,在中序遍历中找到根,根的左边属于根的左子树,根的右边属于根的右子树。
将左子树、右子树看成新的树,在前序遍历中第一个数同样为此树的根节点,重新寻找其左子树和右子树,一直递归寻找
编程
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| function TreeNode(x) { this.val = x; this.left = null; this.right = null; } function reConstructBinaryTree(pre, vin, node) { var Node = node || new TreeNode(pre[0]) var index = vin.indexOf(pre[0]) var preLeft = pre.slice(1, index + 1) var vinLeft = vin.slice(0, index) var preRight = pre.slice(index + 1, pre.length) var vinRight = vin.slice(index + 1, vin.length) if (preLeft.length > 0) { Node.left = new TreeNode(preLeft[0]) reConstructBinaryTree(preLeft, vinLeft, Node.left) } if (preRight.length > 0) { Node.right = new TreeNode(preRight[0]) reConstructBinaryTree(preRight, vinRight, Node.right) } return Node }
|