105. 从前序与中序遍历序列构造二叉树.md

题目链接:

https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

解法:

/**
 * 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) {
        return build(preorder,0,inorder,0,inorder.length);
    }
    private TreeNode build(int[] preorder,int p,int[] inorder,int i,int j){
        if(j <= i)  return null;
        TreeNode root = new TreeNode(preorder[p]);

        int k = 0;
        while(inorder[k] != root.val){
            k++;
        }
        root.left = build(preorder,p+1,inorder,i,k);
        root.right = build(preorder,p+1+k-i,inorder,k+1,j);
        return root;
    }
}

总结:

自己想想不到,这个东西真的像是高中做函数题目一样,有的题目看了答案还有看好长时间才能看懂,最终考察的就是思维吧,在递归条件的推进中,不是特别理解,但是早上起来的脑子已经累了,这道题目加上后面的从中序和后序求出树必须掌握的。