创建／序列化

Construct Binary Tree from Preorder and Inorder Traversal

• 技巧就在于helper method里preorder只需要纪录一个index,也就是每次循环的root,但是需要记录inorder的begin, end

• private TreeNode buildTree(int[] preorder, int pre_index, int[] inorder, int in_start, int in_end)

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTree(preorder, 0, inorder, 0, inorder.length - 1);
    }
    private TreeNode buildTree(int[] preorder, int pre_index, int[] inorder, int in_start, int in_end){
        if(pre_index >= preorder.length || in_start > in_end) return null;
        int rootVal = preorder[pre_index];
        int pos = in_start;
        while(pos <= in_end && inorder[pos] != rootVal){
            pos++;
        }
        int leftTreeLength = pos - in_start;
        TreeNode root = new TreeNode(rootVal);
        root.left = buildTree(preorder, pre_index + 1, inorder, in_start, pos - 1);
        root.right = buildTree(preorder, pre_index + leftTreeLength + 1, inorder, pos + 1, in_end);
        return root;
    }
}

2018/09/10

• 笨方法， 存了prestart, preend, in_start, in_end

• private TreeNode buildTree(int[] preorder, int[] inorder, int preBegin, int preEnd, int inBegin, int inEnd)

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTree(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }
    private TreeNode buildTree(int[] preorder, int[] inorder, int preBegin, int preEnd, int inBegin, int inEnd) {
        if (preBegin > preEnd || preBegin >= preorder.length) return null;
        TreeNode root = new TreeNode(preorder[preBegin]);
        int rootIdx = findRootIndex(inorder, inBegin, inEnd, root.val);
        if (rootIdx == -1) return null;
        root.left = buildTree(preorder, inorder, preBegin + 1, preBegin + rootIdx - inBegin, inBegin, rootIdx - 1);
        root.right = buildTree(preorder, inorder, preBegin + rootIdx - inBegin + 1, preEnd, rootIdx + 1, inEnd);
        return root;
    }
    private int findRootIndex(int[] inorder, int begin, int end, int val) {
        while (begin <= end) {
            if (inorder[begin] == val) {
                return begin;
            } else {
                begin++;
            }
        }
        return -1;
    }
}

Construct Binary Tree from Inorder and Postorder Traversal

• 只需要记录post_index, in_start, in_end三个变量

public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder == null || postorder == null || inorder.length == 0 || postorder.length == 0) return null;
        return buildTree(inorder, 0, inorder.length - 1, postorder, postorder.length - 1);
    }
    private TreeNode buildTree(int[] inorder, int in_start, int in_end, int[] postorder, int post_index){
        if(post_index < 0 || in_start > in_end) {
          return null;
        }

        int in_index = in_start;
        while(in_index <= in_end && inorder[in_index] != postorder[post_index]){
            in_index++;
        }
        int right_length = in_end - in_index;

        TreeNode root = new TreeNode(postorder[post_index]);
        root.left = buildTree(inorder, in_start, in_index - 1, postorder, post_index - right_length - 1);
        root.right = buildTree(inorder, in_index + 1, in_end, postorder, post_index - 1);
        return root;
    }
}

Serialize and Deserialize Binary Tree

• 用 Queue实现bfs

• 注意deserialize的时候，先poll from queue,然后判断String[] input接下来的两个是否为空，只有在不为空的时候才需要append

// Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) return "";
        StringBuilder sb = new StringBuilder();


        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
          TreeNode node = queue.poll();
          if(node == null) {
            sb.append("null ");
            continue;
          }
          sb.append(node.val + " ");
          queue.offer(node.left);
          queue.offer(node.right);
        }
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == "") return null;
        Queue<TreeNode> queue = new LinkedList<>();
        String[] values = data.split(" ");
        TreeNode root = new TreeNode(Integer.parseInt(values[0]));
        queue.offer(root);
        for(int i = 1; i < values.length; i++) {
          TreeNode parent = queue.poll();
          if(!values[i].equals("null")) {
            TreeNode left = new TreeNode(Integer.parseInt(values[i]));
            parent.left = left;
            queue.offer(left);
          }
          if(!values[++i].equals("null")) {
            TreeNode right = new TreeNode(Integer.parseInt(values[i]));
            parent.right = right;
            queue.offer(right);
          }
        }
        return root;
    }