iT邦幫忙

2025 iThome 鐵人賽

DAY 0
0
自我挑戰組

Leetcode30天挑戰系列 第 6

Day6-Construct Binary Tree from Preorder and Inorder Traversal

  • 分享至 

  • xImage
  •  

今天的題目為105.Construct Binary Tree from Preorder and Inorder Traversal,題目再叫我們以前序和 中序的結果,重建原本的二元樹結構。

以下為程式碼以及解說:

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    private Map<Integer, Integer> inorderIndexMap; // 儲存中序遍歷中每個值的位置
    private int preorderIndex = 0; // 用來追蹤目前處理到的前序節點

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        inorderIndexMap = new HashMap<>();
        // 將中序遍歷的值與索引存入 map,方便快速查找
        for (int i = 0; i < inorder.length; i++) {
            inorderIndexMap.put(inorder[i], i);
        }
        // 從整個範圍開始建樹
        return buildSubTree(preorder, 0, inorder.length - 1);
    }

    private TreeNode buildSubTree(int[] preorder, int left, int right) {
        // 如果左邊界超過右邊界,表示這部分沒有節點
        if (left > right) return null;

        // 取得目前的根節點值(來自前序遍歷)
        int rootVal = preorder[preorderIndex++];
        TreeNode root = new TreeNode(rootVal);

        // 在中序遍歷中找到根節點的位置
        int inorderIndex = inorderIndexMap.get(rootVal);

        // 遞迴建構左子樹與右子樹
        root.left = buildSubTree(preorder, left, inorderIndex - 1);
        root.right = buildSubTree(preorder, inorderIndex + 1, right);

        return root;
    }
}

我覺得今天的也有點難,前、中序要搞清楚才行


上一篇
Day5-Maximum Depth of Binary Tree
下一篇
Day7-Construct Binary Tree from Inorder and Postorder Traversal
系列文
Leetcode30天挑戰15
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言