美文网首页
07-重建二叉树

07-重建二叉树

作者: 一方乌鸦 | 来源:发表于2020-05-05 21:59 被阅读0次

    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;
      }
    }
    
    1. 迭代
    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;
        }
    }
    

    相关文章

      网友评论

          本文标题:07-重建二叉树

          本文链接:https://www.haomeiwen.com/subject/cvciwhtx.html