中序遍歷是指二叉樹的遍歷順序,先訪問左子樹,再訪問根節點,最后訪問右子樹。后序遍歷是指二叉樹的遍歷順序,先訪問左子樹,再訪問右子樹,最后訪問根節點。在使用Java編程中,有時需要根據已知的中序遍歷和后序遍歷結果構建二叉樹。
public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } public TreeNode buildTree(int[] inorder, int[] postorder) { if (inorder == null || postorder == null || inorder.length != postorder.length) { return null; } HashMapvalueIndexMap = new HashMap<>(); for (int i = 0; i< inorder.length; i++) { valueIndexMap.put(inorder[i], i); } return buildTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1, valueIndexMap); } private TreeNode buildTree(int[] inorder, int inorderStart, int inorderEnd, int[] postorder, int postorderStart, int postorderEnd, HashMap valueIndexMap) { if (inorderStart >inorderEnd || postorderStart >postorderEnd) { return null; } int rootValue = postorder[postorderEnd]; int rootIndex = valueIndexMap.get(rootValue); TreeNode root = new TreeNode(rootValue); root.left = buildTree(inorder, inorderStart, rootIndex - 1, postorder, postorderStart, postorderStart + rootIndex - inorderStart - 1, valueIndexMap); root.right = buildTree(inorder, rootIndex + 1, inorderEnd, postorder, postorderStart + rootIndex - inorderStart, postorderEnd - 1, valueIndexMap); return root; }
以上代碼是構建二叉樹的函數,使用中序遍歷和后序遍歷的結果作為輸入,返回根節點TreeNode。首先創建一個HashMap,將中序遍歷結果的值和索引存儲在其中,方便后續遍歷時查找節點。接下來通過遞歸不斷構建左右子樹,最后返回根節點。在構建左右子樹時,需要注意中序遍歷和后序遍歷結果的長度計算。
上一篇php array 查詢
下一篇php array 替換