算法第十六天|二叉树-补

106. 从中序与后序遍历序列构造二叉树

 public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || postorder == null) {
            return null;
        }
        return getNodeByTree(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }

    private TreeNode getNodeByTree(int[] inorder, int inorderBegin, int inorderEnd, int[] postorder, int postorderBegin, int postorderEnd) {
        // 根节点没有左子树和没有右子树的情况，需要直接返回
        if (inorderBegin < 0 || inorderEnd > inorder.length || postorderBegin > postorderEnd) {
            return null;
        }
        // 叶子节点
        if (inorderBegin == inorderEnd) {
            return new TreeNode(inorder[inorderBegin]);
        }

        int rootNodeValue = postorder[postorderEnd]; // 1.从后续遍历中找到当前的根节点

        // 2.为根节点创建对象
        TreeNode root = new TreeNode(rootNodeValue);

        // 3. 从前序遍历中找到根节点的下标
        int rooIndex = 0;
        for (rooIndex = inorderBegin; rooIndex <= inorderEnd; rooIndex++) {
            if (rootNodeValue == inorder[rooIndex]) {
                break;
            }
        }

        // 4. 根据根节点位置就可以确定前序遍历当前节点的左子树和右子树起始位置和结束位置
        int preLeftBeginIndex = inorderBegin;
        int preLeftEndIndex = rooIndex - 1;
        int preRightBeginIndex = rooIndex + 1;
        int preRightEndIndex = inorderEnd;


        // 5. 后续遍历中，先是其左子树，然后是右子树，最后是根节点
        // 因为是同一颗二叉树，那么左子树的节点个数是相同的
        // 那么从左往右，先是preLeftEndIndex-preLeftBeginIndex个节点为左子树，然后是preRightEndIndex-preRightBeginIndex个节点为右子树,最后一个为根节点
        int postLeftBeginIndex = postorderBegin;
        int postLeftEndIndex = postLeftBeginIndex  + preLeftEndIndex - preLeftBeginIndex;
        int postRightBeginIndex = postLeftEndIndex + 1;
        int postRightEndIndex = postorderEnd -1;

        root.left = getNodeByTree(inorder, preLeftBeginIndex, preLeftEndIndex, postorder, postLeftBeginIndex, postLeftEndIndex);
        root.right = getNodeByTree(inorder, preRightBeginIndex, preRightEndIndex, postorder, postRightBeginIndex, postRightEndIndex);

        return root;
    }

详细解法已经在代码中进行了标注

105. 从前序与中序遍历序列构造二叉树

  public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null) {
            return null;
        }
        return getTreeNode(preorder, 0, preorder.length -1, inorder, 0, inorder.length -1);
    }

    private TreeNode getTreeNode(int[] preorder, int preBegin, int preEnd, int[] inorder, int inBegin, int inEnd) {
        // 排除掉左右子树为空的情况
        if (preBegin < 0 || preBegin > preEnd || inBegin > inEnd) {
            return null;
        }

        int rootValue = preorder[preBegin]; //根节点的值

        // 叶子节点
        if(preBegin == preEnd) {
            return new TreeNode(rootValue); // 前序遍历最前面是叶子节点
        }

        TreeNode root = new TreeNode(rootValue);


        int rootIndex = 0; // 找到中序遍历中根节点的下标
        for(rootIndex = inBegin; rootIndex <=inEnd; rootIndex++) {
            if (inorder[rootIndex] == rootValue) {
                break;
            }
        }

        int inLeftBeginIndex = inBegin;
        int inLeftEndIndex = rootIndex -1;
        int inRightBeginIndex = rootIndex + 1;
        int inRightEndIndex = inEnd;

        // 前序遍历最开始的元素是根节点，然后是左子树，最后是右子树

        int preLeftBeginIndex = preBegin + 1;
        int preLeftEndIndex = preLeftBeginIndex + inLeftEndIndex - inLeftBeginIndex;
        int preRightBeginIndex = preLeftEndIndex + 1;
        int preRightEndIndex = preEnd;


        root.left = getTreeNode(preorder, preLeftBeginIndex, preLeftEndIndex, inorder, inLeftBeginIndex, inLeftEndIndex);
        root.right = getTreeNode(preorder, preRightBeginIndex, preRightEndIndex,inorder,inRightBeginIndex, inRightEndIndex);

        return root;
    }

相同的配方、相同的味道

最大二叉树

 public TreeNode constructMaximumBinaryTree(int[] nums) {
        if (nums == null) {
            return null;
        }
        return getMaxTreeNode(nums, 0 , nums.length -1);
    }

    private TreeNode getMaxTreeNode(int[] nums, int beginIndex, int endIndex) {
        if (beginIndex > endIndex || beginIndex < 0 || endIndex > nums.length - 1) {
            return null;
        }
        if (beginIndex == endIndex) {
            return new TreeNode(nums[beginIndex]);
        }

        // 获取最大值的下标
        int maxIndex = getMaxIndex(nums, beginIndex, endIndex);

        TreeNode root = new TreeNode(nums[maxIndex]);
        root.left = getMaxTreeNode(nums, beginIndex, maxIndex - 1);
        root.right = getMaxTreeNode(nums, maxIndex + 1, endIndex);

        return root;
    }

    private int getMaxIndex(int[] nums, int left, int right) {
        // 进入的left必然有left>=right
        int maxIndex = left;
        for (int i = left; i <= right; i++) { // 注意这里要等于,这是下标
            maxIndex = nums[i] > nums[maxIndex] ? i : maxIndex;
        }
        return maxIndex;
    }