輸入某二叉樹(shù)的前序遍歷和中序遍歷的結(jié)果，請(qǐng)重建出該二叉樹(shù)。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹(shù)并返回。

?

示例1

??輸入

? ??[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]

返回值

??{1,2,5,3,4,6,7}

class TestTreeNode2 {static TreeNode findBinaryTree(int[] pre, int preStart, int preEnd, int[] in ,int inStart, int inEnd){if(preStart > preEnd || inStart > inEnd)return null;TreeNode root = new TreeNode(pre[preStart]);for(int i = inStart; i<=inEnd; i++){if(in[i] == pre[preStart]){// 左子樹(shù)的長(zhǎng)度為i-inStartroot.left = findBinaryTree(pre, preStart+1,preStart+i-inStart, in, inStart,i-1);root.right = findBinaryTree(pre, preStart+i-inStart+1,preEnd, in, i+1,inEnd);}}return root;}// 重建主函數(shù)public static TreeNode reConstructBinaryTree(int [] pre,int [] in) {TreeNode root = findBinaryTree(pre, 0, pre.length-1, in, 0, in.length-1);return root;}public static void main(String[] args) {int[] pre = new int[]{1,2,4,3,5,6}; // 前序序列 前序序列的第一個(gè)為根節(jié)點(diǎn)int[] in = new int[]{4,2,1,5,3,6}; // 中序序列 根節(jié)點(diǎn)的左邊為左子樹(shù),右邊為右子數(shù)TreeNode root = reConstructBinaryTree(pre,in);showPreTree(root);}static void showPreTree(TreeNode node){if(null == node){return ;}System.out.println(node.val);if(null != node.left){showPreTree(node.left);}if(null != node.right){showPreTree(node.right);}} }

?

?

總結(jié)

以上是生活随笔為你收集整理的常考数据结构与算法:重建二叉树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。