luckydog

V1

2022/03/17阅读:40主题:默认主题

Code_105

先序和中序构造二叉树

code_105

  • tips : 先序,后序不能确定二叉树。

思路

先序 : 根--左--右
中序:左--根--右
在先序中找根分割中序为左右子树,再去找左右子树的跟再分割,可以递归实现。

实现

  • 建树函数返回所见树的根节点,所需参数:先序数组,中序数组,两个数组的left,right索引。
  • HashMap存储中序的值和对应索引,方便分割中序数组。
  • preLeft =
  • 左子树的inRight = HashMap.get(preOrder[preLeft]) - 1
  • 左子树的inLeft = 0
  • 左子树的preLeft = preLeft + 1
  • 左子树的PreRight = HashMap.get(preOrder[preLeft])
  • 右子树 inLeft = HashMap.get(preOrder[preLeft]) + 1
  • 右子树的inRight = n - 1
  • 右子树的preLeft = HashMap.get(preOrder[preLeft]) + 1
  • 右子树的PreRight = n - 1
HashMap<Integer, Integer> hashMap;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        hashMap = new HashMap<>();
        for (int i = 0; i < preorder.length; i++) {
            hashMap.put(inorder[i], i);
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }

    public TreeNode myBuildTree(int[] preorder,
    int[] inorder, int leftPreorder,
    int rightPreorder, int leftInorder, int rightInorder) {
        if (leftPreorder > rightPreorder) {
            return null;
        }
        int preOrderRoot = leftPreorder;
        int inOrderRoot = hashMap.get(preorder[preOrderRoot]);
        TreeNode node = new TreeNode(preorder[preOrderRoot]);
        
        int leftTreeSize = inOrderRoot - leftInorder;
        
        node.left = myBuildTree(preorder, inorder, 
        leftPreorder + 1,
        leftPreorder + leftTreeSize, 
        leftInorder,
        inOrderRoot - 1);

        node.right = myBuildTree(preorder, inorder,
        leftPreorder + leftTreeSize + 1,
        rightPreorder, 
        inOrderRoot + 1, 
        rightInorder);
        
        return node;
    }

分类:

后端

标签:

Java

作者介绍

luckydog
V1