【每日阅读】2020年11月11日-从前序与中序遍历序列构造二叉树

链接

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; }
 * }
 */
import java.util.Arrays;

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length == 0) {
            return null;
        }

        int rootNum = preorder[0];

        // 根节点在中序遍历结果中的index
        int rootAtInOrderIndex = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == rootNum) {
                rootAtInOrderIndex = i;
            }
        }

        TreeNode root = new TreeNode(rootNum);
        root.left = buildTree(Arrays.copyOfRange(preorder, 1, rootAtInOrderIndex + 1),
                Arrays.copyOfRange(inorder, 0, rootAtInOrderIndex));
        root.right = buildTree(Arrays.copyOfRange(preorder, rootAtInOrderIndex + 1, preorder.length),
                Arrays.copyOfRange(inorder, rootAtInOrderIndex + 1, inorder.length));

        return root;
    }
}