LeeCode 二叉树问题（二）

二叉树的构建

LeeCode 106: 从中序遍历与后续遍历序列构造二叉树

题目描述

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

建立模型

中序遍历和后续遍历数组可以唯一确定二叉树。

中序遍历数组：[左，根，右]

后续遍历数组：[左，右，根]

通过后续遍历数组获取根节点的值，然后在中序遍历中找到根节点的下标
通过根节点的下标与数组的左边界计算左子树节点的个数
递归地构造左右子树

代码实现

public TreeNode buildTree(int[] inorder, int[] postorder) {

}

// 包含左边界，不包含右边界 [inStart, inEnd)

public TreeNode buildTreeImpl(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {

  if (inStart >= inEnd) {

    return null;

  }

  int rootVal = postorder[postEnd - 1];

  TreeNode root = new TreeNode(rootVal);

  int rootInorderIndex = 0;

  for (int i = inStart, i < inEnd; i++) {

    if (inorder[i] == root.val) {

      rootInorderIndex = i;

      break;

    }

  }

  int leftTreeSize = rootInorderIndex - inStart;

  root.left = buildTreeImpl(inorder, inStart, rootInorderIndex, postorder, postStart, postStart + leftTreeSize);

  root.right = buildTreeImpl(inorder, rootInorderIndex + 1, inEnd, postorder, postStart + leftTreeSize, postEnd - 1);

}

LeeCode 654: 最大二叉树

题目描述

给定一个不重复的整数数组 nums。最大二叉树可以用下面的算法从 nums 递归地构建：

创建一个根节点，其值为 nums 中的最大值。
递归地在最大值左边的子数组前缀上构建左子树
递归地在最大值右边的子数组后缀上构建右子树

返回 nums 构建的最大二叉树。

代码实现

public TreeNode constructMaximumBinaryTree(int[] nums) {

}

public TreeNode constructMaximumBinaryTreeImpl(int[] nums, int start, int end) {

  if (start >= end) {

    return null;

  }

  int rootVal = Integer.MIN_VALUE;

  int rootIndex = 0;

  for (int i = start, i < end; i++) {

    if (nums[i] > rootVal) {

      rootVal = nums[i];

      rootIndex = i;

    }

  }

  // 构造根节点

  TreeNode root = new TreeNode(rootVal);

  root.left = constructMaximumBinaryTreeImpl(nums, start, rootIndex);

  root.right = constructMaximumBinaryTreeImpl(nums, rootIndex + 1, end);

  return root;

}

LeeCode 二叉树问题（二）的相关教程结束。