重建二叉樹
題目：輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹，假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字，例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并回傳，
分析：
前序遍歷：先訪問根à前序遍歷左子樹à前序遍歷右子樹
中序遍歷：先中序遍歷左子樹à訪問根à中序遍歷右子樹
后序遍歷：先后序遍歷左子樹à后序遍歷右子樹à訪問根
此題有前序和中序：
前：pre:{1,2,4,7,3,5,6,8}
中：vin:{4,7,2,1,5,3,8,6}
根：pre[0]à1，index為3
左子樹：vin_left{4,7,2} pre_left:{2,4,7}
右子樹：vin_right{5,3,8,6} pre_right{3,5,6,8}
然后遞回找出左子樹和右子樹
/* function TreeNode(x) { this.val = x; this.left = null; this.right = null; } */ function reConstructBinaryTree(pre, vin) { // write code here if(pre.length==0||vin.length==0){ return null } const index=vin.indexOf(pre[0]) const left=vin.slice(0,index) const right=vin.slice(index+1) return { val:pre[0], left:reConstructBinaryTree(pre.slice(1,index+1),left), right:reConstructBinaryTree(pre.slice(index+1),right)
} }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/27637.html
標籤：其他
上一篇：CVTE電話面
下一篇：TCP三次握手有哪些漏洞？