07-重建二叉树

https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/solution/mian-shi-ti-07-zhong-jian-er-cha-shu-by-leetcode-s/

1. 递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
  int preIndex = 0;
  int[] preorder;
  int[] inorder;
  public TreeNode buildTree(int[] preorder, int[] inorder) {
    if (preorder == null || inorder == null || preorder.length == 0 || preorder.length != inorder.length) return null;
    this.preorder = preorder;
    this.inorder = inorder;
    return buildTree(0, inorder.length);
  }
  // [inStart, inEnd)
  public TreeNode buildTree(int inStart, int inEnd) {
    if (inStart >= inEnd) return null;
    TreeNode root = new TreeNode(preorder[preIndex++]);
    int index = indexOf(root.val, inStart, inEnd);
    root.left = buildTree(inStart, index);
    root.right = buildTree(index + 1, inEnd);
    return root;
  }

  private int indexOf(int target, int inStart, int inEnd) {
    for (int i = inStart; i < inEnd; i++) {
      if (target == inorder[i]) return i;
    }
    return -1;
  }
}

2. 迭代

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        int length = preorder.length;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        int inorderIndex = 0;
        for (int i = 1; i < 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.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                    node = stack.pop();
                    inorderIndex++;
                }
                node.right = new TreeNode(preorderVal);
                stack.push(node.right);
            }
        }
        return root;
    }
}