主要说一下递归建树的方法:
递归终止条件:前序遍历的左指针大于前序遍历的右指针。
接下来需要做以下事情:
1. 从前序遍历中找到根节点root
2. 从中序遍历中找出根节点root的下标rootIndex,此时[in_left, rootIndex-1]就是root的左子树中的元素;
同理,[rootIndex+1,in_right]就是root的右子树的元素。
3. 记左子树的元素个数为offset,那么左子树的前序序列为[pre_left+1, preleft+offset]; 同理,右子树的前序序列为[pre_left+offset+1,pre_right]。
4. 在已知了上述信息后,每次使用可以创建出根节点和划分左右子树;这样递归下去,最终可自底向上构建出一棵二叉树。
代码如下:
TreeNode build(int pre_left, int pre_right, int in_left, int in_right) { if (pre_left > pre_right) { return null; } TreeNode root = new TreeNode(pre[pre_left]); int rootIndex; // 找到根节点在中序遍历中的下标 for (rootIndex = in_left; rootIndex < in_right; rootIndex++) { if (in[rootIndex] == root.val) { break; } } int offset = rootIndex - in_left; // 得到左子树的元素个数 root.left = build(pre_left + 1, pre_left + offset, in_left, rootIndex - 1); // 递归构建左子树 root.right = build(pre_left + offset + 1, pre_right, rootIndex + 1, in_right); // 递归构建右子树 return root; }