面试题07. 重建二叉树

秒速五厘米 2023-05-28 11:15 2阅读 0赞

# 题目： #

[面试题07. 重建二叉树][07.]  
[105. 从前序与中序遍历序列构造二叉树][105.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]

# 题解： #

[105. 从前序与中序遍历序列构造二叉树][105. 1]  
preorder第一个元素为root，在inorder里面找到root，在它之前的为左子树（长度：L1），之后为右子树（长度：L2）。preorder\[1\]到preorder\[L1\]为左子树，之后为右子树，分别递归。

# 代码： #

/** * 面试题07 */
    import java.util.*;
    
    public class 面试题07 { 
    
        public static TreeNode buildTree(int[] preorder, int[] inorder) { 
            if(preorder.length == 0 || inorder.length == 0)
            { 
                return null;
            }
            TreeNode root = new TreeNode(preorder[0]);
            int index = -1;
            for(int i = 0; i < inorder.length; i++)
            { 
                if(inorder[i] == preorder[0])
                { 
                    index = i;
                    break;
                }
            }
    
            // 注意：preorder.length 与 inorder.length 相等
            root.left = buildTree(Arrays.copyOfRange(preorder, 1, index + 1), Arrays.copyOfRange(inorder, 0, index));
            root.right = buildTree(Arrays.copyOfRange(preorder, index + 1, preorder.length), Arrays.copyOfRange(inorder, index + 1, inorder.length));
    
            return root;
        }
    
        public static void main(String[] args) { 
            int preorder[] = {  3, 9, 20, 15, 7 };
            int inorder[] = {  9, 3, 15, 20, 7 };
            TreeNode tree = buildTree(preorder, inorder);
            System.out.println("***************************************");
            TreeOperation.show(tree);
            System.out.println("***************************************");
        }
        
    }

# 参考： #

1.  [面试题07. 重建二叉树（递归法，清晰图解）][07. 1]
2.  [二叉树的前序遍历（分治思想）][Link 1]
3.  [关于Java中的Arrays.copyOfRange()方法][Java_Arrays.copyOfRange]

[07.]: https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/
[105.]: https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70]: /images/20230528/ff23f28e075e4971af295ce3b0286ca2.png
[105. 1]: https://blog.csdn.net/zyx_ly/article/details/104418357
[07. 1]: https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/solution/mian-shi-ti-07-zhong-jian-er-cha-shu-di-gui-fa-qin/
[Link 1]: https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/solution/er-cha-shu-de-qian-xu-bian-li-fen-zhi-si-xiang-by-/
[Java_Arrays.copyOfRange]: https://blog.csdn.net/babylorin/article/details/67637454