Java是一門廣泛應用于計算機編程領域的語言,不僅非常適合開發Web、移動設備和桌面應用程序,而且還可以用于創建數據結構,特別是二叉樹。下面我們將介紹如何使用中根和后跟來創建二叉樹。
public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public TreeNode buildTree(int[] inorder, int[] postorder) { return build(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1); } public TreeNode build(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) { if (inStart >inEnd) return null; int rootVal = postorder[postEnd]; TreeNode root = new TreeNode(rootVal); int index = 0; for (int i = inStart; i<= inEnd; i++) { if (inorder[i] == rootVal) { index = i; break; } } int leftSize = index - inStart; root.left = build(inorder, inStart, index - 1, postorder, postStart, postStart + leftSize - 1); root.right = build(inorder, index + 1, inEnd, postorder, postStart + leftSize, postEnd - 1); return root; }
該代碼中的buildTree方法接受兩個數組作為參數:inorder和postorder。其中,inorder是中根序列,postorder是后跟序列。該方法返回一個二叉樹,該樹的根節點的值為postorder數組的最后一個元素(后跟序列中最后一個元素就是根節點)。build方法是實際構建二叉樹的方法,它接受6個參數:中根序列的開始位置和結束位置(即inStart和inEnd)、后跟序列的開始位置和結束位置(即postStart和postEnd)以及根節點的值(即postorder的最后一個元素)。
在build方法中,首先判斷中根序列的開始位置是否大于結束位置,如果是,則返回null表示該子樹為空。否則,根據后跟序列的最后一個元素創建根節點。接下來,在中根序列中查找根節點,這可以通過遍歷inorder數組來實現。在找到根節點的位置之后,計算出左子樹的大小,然后遞歸地構建左子樹和右子樹。遞歸要注意更新中根序列和后跟序列的范圍。
下一篇css中調整按鈕大小