色婷婷狠狠18禁久久YY,CHINESE性内射高清国产,国产女人18毛片水真多1,国产AV在线观看

JAVA已知中序和后序遍歷

張明哲1年前7瀏覽0評論

中序遍歷是指二叉樹的遍歷順序,先訪問左子樹,再訪問根節點,最后訪問右子樹。后序遍歷是指二叉樹的遍歷順序,先訪問左子樹,再訪問右子樹,最后訪問根節點。在使用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, 
HashMapvalueIndexMap) {
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,將中序遍歷結果的值和索引存儲在其中,方便后續遍歷時查找節點。接下來通過遞歸不斷構建左右子樹,最后返回根節點。在構建左右子樹時,需要注意中序遍歷和后序遍歷結果的長度計算。