06. 前序+中序重建二叉树 ---剑指Offer(Java版)

刺骨的言语ヽ痛彻心扉 2022-03-10 06:14 139阅读 0赞

[<剑指Offer>(Java版)：github][Offer_Java_github]

> 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8\}和中序遍历序列\{4,7,2,1,5,3,8,6\}，则重建二叉树并返回。

前序+中序 == 树的结构

推导过程：

> 首先前序的第一个是根节点： 1
> 
> 然后在中序中找到1，\{4,7,2\}在其左侧：即根的左侧，\{5,3,8,6\}在其右侧，即根的右侧.
> 
> 其中2是\{4,7,2\}中前序最靠前的，所有2是根节点的左节点，\{4,7\}都在 2 的右侧.
> 
> 同理，4是2的左节点，7是4的右节点.
> 
> 也就是:
> 
>             \{1\}
> 
>        \{2\}
> 
> \{4\}
> 
>      \{7\}

> \{5,3,8,6\}通过前序可以被拆分为：
> 
> \{5\},\{3\},\{8,6\}
> 
>      \{3\},
> 
> \{5\},   \{6\},
> 
>             \{8\}

把上述过程转化成代码即可

> 在目标中序数组中找到前序中最靠前的数字，然后依靠这个数字将目标切割为两个目标中序数组，左侧的数组在目标数字的左侧，右侧数组在目标数字中的右侧.
> 
> 循环上述步骤.

因为目标数组不断的变小，所以使用递归更简单一些。

/**
     * 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
     * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
     * 例如
     * 输入前序遍历序列{1,2,4,7,3,5,6,8}；
     * 中序遍历序列{4,7,2,1,5,3,8,6}，
     * 则重建二叉树并返回。
     */
    public class _006_reConstructBinaryTree {
        /**
         * 前序+中序----》二叉树
         * 使用前序找到root节点，找到其在中序中的对应位置；
         * 那么在中序中：root左侧为左子树，右侧为右子数。
         * 递归重复以上过程即可
         */
    
        public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
            // 真正有用的不是前序数组，而是数组在前序中出现的次序。
            int[] index = new int[pre.length];
            // 找到前序对应在中序中的顺序,使用index数组保存.
            for (int i = 0; i < pre.length; i++) {
                for (int j = 0; j < in.length; j++) {
                    if (pre[i] == in[j]) {
                        index[j] = i;
                    }
                }
            }
            // 初始化完毕，前序已经呗转化为了其对应的中序的位置。
            TreeNode root = reConstructBinaryTree(in, index, 0, index.length - 1);
            return root;
        }
    
        private TreeNode reConstructBinaryTree(int[] in, int[] index, int head, int last) {
            if (head > last) {
                return null;
            }
            int minIndex = head;
            // 找到目标中序数组中且在前序数组中最靠前的数字.
            for (int i = head + 1; i <= last; i++) {
                if (index[minIndex] > index[i]) {
                    minIndex = i;
                }
            }
            // 通过数字生成新节点。
            TreeNode root = new TreeNode(in[minIndex]);
            // 递归处理其左侧数组和右侧数组
            root.left = reConstructBinaryTree(in, index, head, minIndex - 1);
            root.right = reConstructBinaryTree(in, index, minIndex + 1, last);
            return root;
        }
    }

[Offer_Java_github]: https://github.com/RudBob/offer66