剑指Offer07. 重建二叉树

题目描述

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

示例 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

JAVA代码

递归方法

参考了天勤书内的解法。

**设计思想：**先序遍历序列中第一个元素x即为树的根结点数值。在中序遍历中找到x，利用x将中序遍历的数组分为了两个子序列，左边序列构成树的左子树，右边序列构成树的右子树，再对左右两个子序列用同样的方法处理，直到处理的子序列只剩下一个元素时，二叉树构造完成。

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
    
        int n = preorder.length;
        TreeNode node = createTree(preorder,inorder,0,n-1,0,n-1);
        return node;
    }

	//构建二叉树
    public TreeNode createTree(int[] preorder, int[] inorder,int L1,int R1,int L2,int R2){
    
        TreeNode node;
        int i;
        if(L1>R1){
    
            return null;
        }
        node = new TreeNode();
        node.left=node.right=null;
        for(i = L2;i<=R2;++i){
    
            if(inorder[i]==preorder[L1]){
    
                break;
            }
        }
        node.val = inorder[i];
        node.left = createTree(preorder,inorder,L1+1,L1+i-L2,L2,i-1);
        node.right = createTree(preorder,inorder,L1+i-L2+1,R1,i+1,R2);
        return node;
    }
}

官方–迭代方法

迭代即非递归方法。
思路可以二叉树遍历的非递归实现作为理论基础。
二叉树的非递归方法感觉很难理解，故待后续有学习需求再来这里补充。
暂时感觉递归够用。看不懂所以不纠结浪费时间了。