題目:給定二叉樹的前序遍歷和中序遍歷,生成二叉樹。
Example:
前序遍歷數組:preArr[]:{1,2,4,5,3,6,7}
中序遍歷數組:inArr[]:{4,2,5,1,6,3,7}
生成的二叉樹如下圖:
解題思路:
由二叉樹的前序變量性質可知:preArr[0] 是數組的根節點,有根據二叉樹的中序遍歷的性質可知,{4,2,5}是二叉樹的左子樹,{6,3,7}在右子樹上,重復執行該操作就構造出了二叉樹
public class Solution { public TreeNode reConstructBinaryTree(int[] pre, int[] in) { TreeNode root = new TreeNode(pre[0]);//前序的第一個數定為根 int len = pre.length; //當只有一個數的時候 if (len == 1) { root.left = null; root.right = null; return root; } //找到中序中的根位置 int rootval = root.val; int i; for (i = 0; i < len; i++) { if (rootval == in[i]) break; } //創建左子樹 if (i > 0) { int[] pr = new int[i]; int[] ino = new int[i]; for (int j = 0; j < i; j++) { pr[j] = pre[j + 1]; } for (int j = 0; j < i; j++) { ino[j] = in[j]; } root.left = reConstructBinaryTree(pr, ino); } else { root.left = null; } //創建右子樹 if (len - i - 1 > 0) { int[] pr = new int[len - i - 1]; int[] ino = new int[len - i - 1]; for (int j = i + 1; j < len; j++) { ino[j - i - 1] = in[j]; pr[j - i - 1] = pre[j]; } root.right = reConstructBinaryTree(pr, ino); } else { root.right = null; } return root; } public static void main(String[] args) { int[] preArr = {1, 2, 4, 5, 3, 6, 7}; int[] inArr = {4, 2, 5, 1, 6, 3, 7}; Solution s = new Solution(); TreeNode root = s.reConstructBinaryTree(preArr, inArr); s.postOrder(root); }