07-重建二叉树

题目描述

https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

示例 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

限制：

0 <= 节点个数 <= 5000

注意：本题与主站 105 题重复：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

思路分析

二叉树的遍历是根据遍历中“根”节点所处的位置，分为前序遍历，中序遍历和后续遍历

前序遍历：顺序为根左右，中序遍历：顺序为左根右

从题目中可以得知前序遍历 [3,9,20,15,7] 说明第一个节点3是根节点，后面为他的子节点。他们他们的子节点是如何分布的。

我们就要看中序遍历，中序遍历为左根右，那么我们找到 3 的位置，位于3左边的就是左子树，位于3右边的就是右子树，如 [9,3,15,20,7]

3 左边是9，右边是 15,20,7 这样经过第一步计算，我们知道了根节点和左右子树。

那么如何构建子树呢，我们会发现，其实拆开的左右子树，又分别是一个子问题，我们从第一个数组中取出前序遍历的结果结合第二个数组的中序结果，又可以构建对应的子树，最终递归到底部，构建出完整的树结构。

【TODO】该题还有迭代解法，参考 https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solution/cong-qian-xu-yu-zhong-xu-bian-li-xu-lie-gou-zao-9/

实现代码

csharp

public class Solution {
    private TreeNode BuildNode(int[] preorder, int preorderStart, int preorderEnd, int[] inorder , int inorderStart, int inorderEnd){
        //Console.WriteLine(preorderStart);
        //Console.WriteLine(preorderEnd);
        if(preorderStart > preorderEnd){
            return null;
        }
        int val = preorder[preorderStart];
        TreeNode node = new TreeNode(val);        
        //构造子树
        //找到中序排列的分界点
        int offset = 0;
        for(int i= inorderStart; i<=inorderEnd; i++){
            if(val != inorder[i]){
                offset++;
            }
            else{
                break;
            }
        }
        //Console.WriteLine("Offset : {0}",offset);
        //offset = 1
        node.left = BuildNode(preorder,preorderStart+1,preorderStart+1+offset-1,inorder,inorderStart,inorderStart+offset-1);
        node.right = BuildNode(preorder,preorderStart+1+offset,preorderEnd,inorder,inorderStart+offset+1,inorderEnd);
        return node;
    }
    //基本思路：
    //前序遍历第一个节点就是 root 然后根据 root 在中序数组中的位置，再构造左子树和右子树
    public TreeNode BuildTree(int[] preorder, int[] inorder) {
        TreeNode root = BuildNode(preorder,0,preorder.Length-1,inorder,0,inorder.Length-1);
        return root;
    }
}

思路分析2：迭代法

preorder = [3,9,20,15,7] inorder = [9,3,15,20,7]

在前序遍历中（根左右），连续的两个数 u,v 那么 v 要么是 u 的左儿子，要么是 u 或者 u 上级的右儿子

那么如何判断他是左儿子，还是某个节点的右儿子呢，我们有一个栈把这些所有没有处理过的节点加入栈。

设中序 inOrderIndex = 0 根据中序遍历的特性（左根右），如果发现栈顶的元素等于中序的当前值 inorder[inOrderIndex] 那么说明找到了当前节点的根，他没有左儿子了，（因为如果他还有左儿子，他会在 inorder的第一个)

那么我们开始构造栈中某个节点的右儿子，但是到底是哪个节点的右儿子呢？我们发现前序节点插入栈内的顺序，恰好应该是中序遍历的倒序，一直到当前节点不相等为止，所以当 inorder[inOrderIndex] == stack.Peek() 的时候，直接弹出节点作为当前节点。如果栈为空，或发现不相等，说明就是当前节点的右儿子。

csharp

public class Solution {
    public TreeNode BuildTree(int[] preorder, int[] inorder) {
        if(preorder.Length == 0 || inorder.Length == 0){
            return null;
        }
        int val = preorder[0];
        TreeNode root = new TreeNode(val);
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.Push(root);
        //遍历前序
        int inOrderIndex = 0;
        for(int i = 1; i < preorder.Length; i++){
            int preOrderVal = preorder[i];
            TreeNode node = stack.Peek();
            //如果栈顶元素和中序遍历的值不同，说明节点存在左子树
            if(node.val != inorder[inOrderIndex]){
                node.left = new TreeNode(preOrderVal);
                stack.Push(node.left);
            }
            else{
                // 当 栈非空 且 栈顶元素的值 与 中序遍历当前所指的值 相同
                while(stack.Count > 0 && inorder[inOrderIndex] == stack.Peek().val){
                    node = stack.Pop();
                    inOrderIndex++;
                }
                // while循环结束后，当前node所指向的节点就是需要重建右子树的节点
                node.right = new TreeNode(preOrderVal);
                stack.Push(node.right);
            }
        }
        return root;
    }
}

07-重建二叉树 #

题目描述 #

思路分析 #

实现代码 #

思路分析2： 迭代法 #

07-重建二叉树

题目描述

思路分析

实现代码

思路分析2：迭代法