[Vssue]0106.从中序与后序遍历序列构造二叉树.md

[youngyangyang04]

https://www.programmercarl.com/0106.%E4%BB%8E%E4%B8%AD%E5%BA%8F%E4%B8%8E%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%E5%BA%8F%E5%88%97%E6%9E%84%E9%80%A0%E4%BA%8C%E5%8F%89%E6%A0%91.html

[Du1in9]

class Solution {
    public TreeNode buildTree(int[] order2, int[] order3) {
        return BuildTree(order2, order3, 0, order2.length - 1, 0, order3.length - 1);
    }

    private TreeNode BuildTree(int[] order2, int[] order3, int start2, int end2, int start3, int end3) {
        if (start2 > end2 || start3 > end3) {
            return null;
        }
        int value = order3[end3];
        TreeNode node = new TreeNode(value);
        int index = start2;
        while (order2[index] != value) {
            index++;
        }
        int size = index - start2;
        node.left = BuildTree(order2, order3, start2, index - 1, start3, start3 + size - 1);
        node.right = BuildTree(order2, order3, index + 1, end2, start3 + size, end3 - 1);
        return node;
    }
}

class Solution {
    public TreeNode buildTree(int[] order1, int[] order2) {
        return BuildTree(order1, order2, 0, order1.length - 1, 0, order2.length - 1);
    }

    private TreeNode BuildTree(int[] order1, int[] order2, int start1, int end1, int start2, int end2) {
        if (start1 > end1 || start2 > end2) {
            return null;
        }
        int value = order1[start1];
        TreeNode node = new TreeNode(value);
        int index = start2;
        while (order2[index] != value) {
            index++;
        }
        int size = index - start2;
        node.left = BuildTree(order1, order2, start1 + 1, start1 + size, start2, index - 1);
        node.right = BuildTree(order1, order2, start1 + size + 1, end1, index + 1, end2);
        return node;
    }
}

[stcirclear]

文章写的很好！之前其实刷过这道题，但是感觉自己总是忘记，又跟着文章思路再写了一遍。感觉这样写符合文章的讲解又更好理解，不需要使用到map。 中序+后序

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(inorder []int, postorder []int) *TreeNode {
    length := len(inorder)
    if length == 0 {
        return nil
    }

    // postorder的最后一个值为根节点
    root := &TreeNode{}
    root.Val = postorder[len(postorder)-1]

    // 根据跟节点的值在中序数组中找到对应位置，并将其分割为左右数组
    index := 0
    for inorder[index] != root.Val && index < len(inorder) {
        index++
    }
    // inorder分成      [0..index)  [index+1..length)
    // postorder分成    [0..index)  [index..length-1)
    root.Left = buildTree(inorder[:index], postorder[:index])
    root.Right = buildTree(inorder[index+1:], postorder[index:length-1])
    return root
}

中序+前序

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(preorder []int, inorder []int) *TreeNode {
    length := len(inorder)
    if length == 0 {
        return nil
    }

    // postorder的最后一个值为根节点
    root := &TreeNode{}
    root.Val = preorder[0]

    // 根据跟节点的值在中序数组中找到对应位置，并将其分割为左右数组
    index := 0
    for inorder[index] != root.Val && index < len(inorder) {
        index++
    }
    // 左闭右开区间符合go silce截取的特性
    // inorder分成      [0..index)    [index+1..length)
    // preorder分成     [1..index+1)  [index+1..length)
    root.Left = buildTree(preorder[1:index+1], inorder[:index])
    root.Right = buildTree(preorder[index+1:], inorder[index+1:])
    return root
}

[JIE-yx]

这道题真的加深了对前、中、后序二叉树遍历的理解

[lzjyyy]

if (inorder.empty() || postorder.empty()) return nullptr;

// 创建根节点 TreeNode* root = new TreeNode(postorder.back()); postorder.pop_back();

// 使用栈来维护节点，并记录已访问的节点 stack<TreeNode*> stk; stk.push(root);

// 使用哈希表加速 inOrder 中节点位置的查找 unordered_map<int, int> inOrderMap; for (size_t i = 0; i < inorder.size(); ++i) { inOrderMap[inorder[i]] = i; }

// 遍历后序遍历数组，构建二叉树 while (!postorder.empty()) { TreeNode* node = stk.top();

// 确保 `postOrderVal` 存在
int postOrderVal = postorder.back();
if (inOrderMap.find(postOrderVal) == inOrderMap.end()) {
    cerr << "Error: Value " << postOrderVal << " not found in inorder map." << endl;
    return nullptr;
}
int postOrderIndex = inOrderMap[postOrderVal];
int inOrderIndex = inOrderMap[node->val];

if (postOrderIndex > inOrderIndex) {
    // postOrderIndex > inOrderIndex 表示这是右子树
    node->right = new TreeNode(postOrderVal);
    stk.push(node->right);
    postorder.pop_back();
} else {
    // 找到对应的左子树
    while (!stk.empty() && inOrderMap[stk.top()->val] > postOrderIndex) {
        node = stk.top();
        stk.pop();
    }
    node->left = new TreeNode(postOrderVal);
    stk.push(node->left);
    postorder.pop_back();
}

} return root;