算法分享（03）：重建二叉树

灰太狼 2024-04-18 09:51 35阅读 0赞

### 题目描述 ###

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

### 思路分析 ###

采用递归算法，依次建立各节点。

### 示例代码 ###

java实现：

/**
     * 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) {
            return reConstructBinaryTree(pre, 0, pre.length - 1, in, 0, in.length -1);
        }
        
        
        public TreeNode reConstructBinaryTree(int [] pre, int preStartIndex, int preEndIndex,int [] in, int inStartIndex, int inEndIndex) {
            //无子树的情况
            if (preStartIndex > preEndIndex || inStartIndex > inEndIndex) return null;
            TreeNode root = new TreeNode(pre[preStartIndex]);
            for (int i = inStartIndex; i <= inEndIndex; i ++) {
                if (pre[preStartIndex] == in[i]){
                    //创建左右子树
                    root.left = reConstructBinaryTree(pre, preStartIndex + 1, preStartIndex + i - inStartIndex, in, inStartIndex, i - 1);
                    root.right = reConstructBinaryTree(pre, i + 1 - inStartIndex + preStartIndex, preEndIndex, in, i + 1, inEndIndex);
                    break;
                }
            }
            return root;
        }
    }

关于创建左右子树的代码解析，参考下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RRV2VpMDAwMDE_size_16_color_FFFFFF_t_70][]

注：已上算法实现方式来源于网络，向贡献者表示感谢。如果读者关于二叉树遍历有不明白的地方，我向大家推荐一本书《大话数据结构》，该书也是我学习算法和数据结构的入门书籍。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RRV2VpMDAwMDE_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/f11e7a2262424683894796f12105bab5.png