讨论/《深度优先搜索》 - 练习:从前序与中序遍历序列构造二叉树/
《深度优先搜索》 - 练习:从前序与中序遍历序列构造二叉树
共 6 个回复
class Solution:
    def buildTree(self, ps: List[int], ins: List[int]) -> TreeNode:
        if ps:
            root = TreeNode(ps[0])   # 前序遍历 第一个 为根节点
            i = ins.index(ps[0])  # 根节点可以作为 中序节点的分割点,左子树i个,右子树剩余的
            root.left = self.buildTree(ps[1:i+1], ins[:i])  # 前序左子树1~i   右子树 i+1~N
            root.right = self.buildTree(ps[i+1:], ins[i+1:])# 中序左子树0~i-1 右子树 i+1~N
            return root
2

【C语言】根据视频讲解和讨论中C语言代码,自己手敲代码。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){
    // 递归结束条件
    if (preorder == NULL || inorder == NULL) {
        return NULL;
    }
    if (preorderSize == 0 || inorderSize == 0) {
        return NULL;
    }
    if (preorderSize != inorderSize) {
        return NULL;
    }
    // 初始化
    struct TreeNode *pTreeNode = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    if (pTreeNode == NULL) {
        return NULL;
    }
    memset(pTreeNode, 0, sizeof(struct TreeNode));
    int rootVal = preorder[0];
    // 查找根节点在中序中索引
    int rootIndex = 0;
    for (int i = 0; i < inorderSize; i++) {
        if (inorder[i] == rootVal) {
            rootIndex = i;
            break;
        } 
    }
    // 递归左子树,右子树
    int rightSize = preorderSize - 1 - rootIndex;
    pTreeNode->val = rootVal;
    pTreeNode->left = buildTree(&preorder[1], rootIndex, &inorder[0], rootIndex);
    pTreeNode->right = buildTree(&preorder[rootIndex + 1], rightSize, &inorder[rootIndex + 1], rightSize);
    return pTreeNode;
}
class Solution {

    Map<Integer, Integer> indexCache = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTree(preorder, 0, preorder.length, inorder, 0, inorder.length);
    }

    private TreeNode buildTree(int[] preorder, int start1, int end1, int[] inorder, int start2, int end2) {
        if (start1 == end1) {
            return null;
        }
       int root = preorder[start1];
       int pos = lookFor(inorder, start2, end2, root);
       int leftNum = pos - start2;
       int split =  start1 + leftNum + 1;
       return new TreeNode(root, buildTree(preorder, start1 + 1, split, inorder, start2, pos), buildTree(preorder, split, end1, inorder, pos + 1, end2));

    }

    private int lookFor(int[] array, int start, int end, int target) {
        Integer index = indexCache.get(target);
        if (index != null) {
            return index;
        }
        for (int i = start; i < end; i++) {
            if (array[i] == target) {
                return i;
            } else {
                indexCache.put(array[i], i);
            }
        }
        return -1;
    }
}
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder or not inorder: return None
        # 性质:前序遍历的第一个元素是根节点
        root_val = preorder[0]
        root = TreeNode(root_val)
        # 性质:中序遍历根元素之前的为左子树的中序遍历,根元素之后的为右子树的中序遍历
        position = inorder.index(root_val)
        # 递归构建左右子树
        root.left = self.buildTree(preorder[1:position+1], inorder[:position])
        root.right = self.buildTree(preorder[position+1:], inorder[position+1:])
        return root
class Solution {
    int pre_index = 0;
    int[] preorder;
    HashMap<Integer, Integer> indexMap = new HashMap<Integer, Integer>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for (int i = 0; i < inorder.length; i++) {
            indexMap.put(inorder[i], i);
        }
        return helper(0, inorder.length);
    }

    public TreeNode helper(int in_left, int in_right) {
        if (in_left == in_right) return null;
        int root_val = preorder[pre_index];
        TreeNode root = new TreeNode(root_val);

        int index = indexMap.get(root_val);

        pre_index++;

        root.left = helper(in_left, index);
        root.right = helper(index + 1, in_right);
            
        return root;
    }
}

强啊