每天一道剑指offer-重建二叉树
重建二叉树
https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=13&tqId=11157&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,2,7,1,5,3,8,6}，则重建二叉树并返回。
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
}解析
先序序列的特点是第一个数就是根结点而后是左子树的先序序列和右子树的先序序列，而中序序列的特点是先是左子树的中序序列，然后是根结点，最后是右子树的中序序列。因此我们可以通过先序序列得到根结点，然后通过在中序序列中查找根结点的索引从而得到左子树和右子树的结点数。然后可以将两序列都一分为三，对于其中的根结点能够直接重建，然后根据对应子序列分别递归重建根结点的左子树和右子树。这是一个典型的将复杂问题划分成子问题分步解决的过程。
递归体的定义，如上图先序序列的左子树序列是 2,3,4对应下标 1,2,3，而中序序列的左子树序列是 3,2,4对应下标 0,1,2，因此递归体接收的参数除了保存两个序列的数组之外，还需要指明需要递归重建的子序列分别在两个数组中的索引范围： TreeNoderebuild(int[]pre,inti,intj,int[]in,intm,intn)。然后递归体根据 pre的 i~j索引范围形成的先序序列和 in的 m~n索引范围形成的中序序列重建一棵树并返回根结点。
首先根结点就是先序序列的第一个数，即 pre[i]，因此 TreeNoderoot=newTreeNode(pre[i])可以直接确定，然后通过在 in的 m~n中查找出 pre[i]的索引 index可以求得左子树结点数 leftNodes=index-m，右子树结点数 rightNodes=n-index，如果左（右）子树结点数为0则表明左（右）子树为 null，否则通过 root.left=rebuild(pre,i' ,j',in,m' ,n')来重建左（右）子树即可。
这个题的难点也就在这里，即 i',j',m',n'的值的确定，笔者曾在此困惑许久，建议通过 leftNodes,rightNodes和 i,j,m,n来确定：（这个时候了前往不要在脑子里面想这些下标对应关系！！一定要在纸上画，确保准确性和概括性）
于是容易得出如下代码：
if(leftNodes == 0){ root.left = null;}else{ root.left = rebuild(pre, i + 1, i + leftNodes, in, m, m + leftNodes - 1);}if(rightNodes == 0){ root.right = null;}else{ root.right = rebuild(pre, i + leftNodes + 1, j, in, n - rightNodes + 1, n);}笔者曾以中序序列的根节点索引来确定 i',j',m',n'的对应关系写出如下错误代码：
if(leftNodes == 0){ root.left = null;}else{ root.left = rebuild(pre, i + 1, index, in, m, index - 1);}if(rightNodes == 0){ root.right = null;}else{ root.right = rebuild(pre, index + 1, j, in, index + 1, n);}这种对应关系乍一看没错，但是不具有概括性（即囊括所有情况），比如对序列 2,3,4、 3,2,4重建时：
你看这种情况，上述错误代码还适用吗？原因就在于 index是在 in的 m~n中选取的，与数组 in是绑定的，和 pre没有直接的关系，因此如果用 index来表示 i',j'自然是不合理的。
此题的正确完整代码如下：
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */public class Solution { public TreeNode reConstructBinaryTree(int [] pre,int [] in) { if(pre == null || in == null || pre.length == 0 || in.length == 0 || pre.length != in.length){ return null; } return rebuild(pre, 0, pre.length - 1, in, 0, in.length - 1); }
public TreeNode rebuild(int[] pre, int i, int j, int[] in, int m, int n){ int rootVal = pre[i], index = findIndex(rootVal, in, m, n); if(index < 0){ return null; } int leftNodes = index - m, rightNodes = n - index; TreeNode root = new TreeNode(rootVal); if(leftNodes == 0){ root.left = null; }else{ root.left = rebuild(pre, i + 1, i + leftNodes, in, m, m + leftNodes - 1); } if(rightNodes == 0){ root.right = null; }else{ root.right = rebuild(pre, i + leftNodes + 1, j, in, n - rightNodes + 1, n); } return root; }
public int findIndex(int target, int arr[], int from, int to){ for(int i = from ; i <= to ; i++){ if(arr[i] == target){ return i; } } return -1; }}总结：
- 对于复杂问题，一定要划分成若干子问题，逐一求解。比如二叉树问题，我们通常将其划分成头结点、左子树、右子树。
- 对于递归过程的参数对应关系，尽量使用和数据样本本身没有直接关系的变量来表示。比如此题应该选取
leftNodes和rightNodes来计算i',j',m',n'而不应该使用头结点在中序序列的下标index（它和in是绑定的，那么可能对pre就不适用了）。
出自：http://www.zhenganwen.top
已获授权