题解 | #牛群的树形结构重建II#
牛群的树形结构重建II
https://www.nowcoder.com/practice/ad81ec30cca0477e82e33334a652a6ae
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param preOrder int整型一维数组 * @param inOrder int整型一维数组 * @return TreeNode类 */ public TreeNode buildTreeII (int[] preOrder, int[] inOrder) { // write code here if (preOrder.length == 0 || inOrder.length == 0) return null; return build(preOrder, inOrder, 0, preOrder.length, 0, inOrder.length); } private TreeNode build(int[] preOrder, int[] inOrder, int preBegin, int preEnd, int inBegin, int inEnd) { if (preBegin == preEnd) return null; int rootVal = preOrder[preBegin]; TreeNode root = new TreeNode(rootVal); if (preEnd - preBegin == 1) return root; int ind = inBegin; for (; ind < inEnd; ++ind) { if (inOrder[ind] == rootVal) break; } // 左闭右开 int leftInBegin = inBegin; int leftInEnd = ind; int rightInBegin = leftInEnd + 1; int rightInEnd = inEnd; int leftPreBegin = preBegin + 1; int leftPreEnd = leftPreBegin + (leftInEnd - leftInBegin); int rightPreBegin = leftPreEnd; int rightPreEnd = preEnd; root.left = build(preOrder, inOrder, leftPreBegin, leftPreEnd, leftInBegin, leftInEnd); root.right = build(preOrder, inOrder, rightPreBegin, rightPreEnd, rightInBegin, rightInEnd); return root; } }
本题知识点分析:
- 基本的Java语法和概念。
- 二叉树的构建和遍历。
- 递归算法的应用。
本题解题思路分析:
在这个实现中,我们首先根据先序遍历数组确定根节点,然后在中序遍历数组中找到根节点的位置,从而将数组分为左子树和右子树部分。然后,我们递归地构建左子树和右子树。
buildTreeHelper方法中,preIndex表示当前在先序遍历数组中的索引,inStart和inEnd表示当前中序遍历数组中的起始和结束索引。我们在中序遍历数组中找到根节点的索引,然后根据该索引将数组分为左右子树,并继续递归地构建这些子树。