MrainW's Home

All things come to those who wait!

0%

Posted on In ,
Symbols count in article: 1.5k Reading time ≈ 1 mins.

Question

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Example 1:

1
2
Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

Example 2:

1
2
Input: root = []
Output: []

Example 3:

1
2
Input: root = [1]
Output: [1]

Solution

  • Solution1 – preorder traversal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return "#";
        return root.val + "," + serialize(root.left) + "," + serialize(root.right);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        Queue<String> q = new LinkedList<>(Arrays.asList(data.split(",")));
        return helper(q);
    }
    private TreeNode helper(Queue<String> q){
        String s = q.poll();
        if (s.equals("#")) return null;
        TreeNode root = new TreeNode(Integer.parseInt(s));
        root.left = helper(q);
        root.right = helper(q);
        return root;
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(n)

Posted on In ,
Symbols count in article: 955 Reading time ≈ 1 mins.

Question

Given the root of a binary tree, return the zigzag level order traversal of its nodes’ values. (i.e., from left to right, then right to left for the next level and alternate between).

Example 1:

1
2
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]

Example 2:

1
2
Input: root = [1]
Output: [[1]]

Example 3:

1
2
Input: root = []
Output: []

Solution

  • Solution1 – BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        if(root != null) q.offer(root);
        while(!q.isEmpty()){
            int size = q.size();
            List<Integer> level = new ArrayList<>();
            for(int i = 0; i < size; i++){
                TreeNode cur = q.poll();
                if (res.size() % 2 == 0) level.add(cur.val);
                else level.add(0, cur.val);
                if(cur.left != null) q.offer(cur.left);
                if(cur.right != null) q.offer(cur.right);
            }
            res.add(level);
        }
        return res;
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(n)

Posted on In ,
Symbols count in article: 868 Reading time ≈ 1 mins.

Question

Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

Example 1:

1
2
Input: root = [3,9,20,null,null,15,7]
Output: [[15,7],[9,20],[3]]

Example 2:

1
2
Input: root = [1]
Output: [[1]]

Example 3:

1
2
Input: root = []
Output: []

Solution

  • Solution1 – BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        if(root != null) q.offer(root);
        while(!q.isEmpty()){
            int size = q.size();
            List<Integer> level = new ArrayList<>();
            for(int i = 0; i < size; i++){
                TreeNode cur = q.poll();
                level.add(cur.val);
                if(cur.left != null) q.offer(cur.left);
                if(cur.right != null) q.offer(cur.right);
            }
            res.add(0,level);
        }
        return res;
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(n)

Posted on In ,
Symbols count in article: 866 Reading time ≈ 1 mins.

Question

Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

Example 1:

1
2
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Example 2:

1
2
Input: root = [1]
Output: [[1]]

Example 3:

1
2
Input: root = []
Output: []

Solution

  • Solution1 – iterative
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        if(root != null) q.offer(root);
        while(!q.isEmpty()){
            int size = q.size();
            List<Integer> level = new ArrayList<>();
            for(int i = 0; i < size; i++){
                TreeNode cur = q.poll();
                level.add(cur.val);
                if(cur.left != null) q.offer(cur.left);
                if(cur.right != null) q.offer(cur.right);
            }
            res.add(level);
        }
        return res;
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(n)

Posted on In ,
Symbols count in article: 1.1k Reading time ≈ 1 mins.

Question

Given the root of a binary tree, return the postorder traversal of its nodes’ values.

Example 1:

1
2
Input: root = [1,null,2,3]
Output: [3,2,1]

Example 2:

1
2
Input: root = []
Output: []

Example 3:

1
2
Input: root = [1,2]
Output: [2,1]

Solution

  • Solution1 – iterative
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root != null) stack.push(root);
        while(!stack.isEmpty()){
            root = stack.pop();
            res.add(0, root.val);
            if(root.left != null) stack.push(root.left);
            if(root.right != null) stack.push(root.right);
        }
        return res;
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(n)

  • Solution2 – recursive
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        helper(root, res);
        return res;
    }
    private void helper(TreeNode root, List<Integer> res) {
 		if (root == null) return;
        helper(root.left, res);
        helper(root.right, res);
        res.add(root.val);
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(n)

Posted on In ,
Symbols count in article: 1k Reading time ≈ 1 mins.

Question

Given the root of a binary tree, return the inorder traversal of its nodes’ values.

Example 1:

1
2
Input: root = [1,null,2,3]
Output: [1,3,2]

Example 2:

1
2
Input: root = []
Output: []

Example 3:

1
2
Input: root = [1]
Output: [1]

Solution

  • Solution1 – iterative
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while(root != null || !stack.isEmpty()){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(n)

  • Solution2 – recursive
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        helper(root, res);
        return res;
    }
    private void helper(TreeNode root, List<Integer> res) {
 		if (root == null) return;
        helper(root.left, res);
        res.add(root.val);
        helper(root.right, res);
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(n)

Posted on In ,
Symbols count in article: 1.1k Reading time ≈ 1 mins.

Question

Given the root of a binary tree, return the preorder traversal of its nodes’ values.

Example 1:

1
2
Input: root = [1,null,2,3]
Output: [1,2,3]

Example 2:

1
2
Input: root = []
Output: []

Example 3:

1
2
Input: root = [1]
Output: [1]

Solution

  • Solution1 – iterative
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root != null) stack.push(root);
        while(!stack.isEmpty()){
            root = stack.pop();
            res.add(root.val);
            if(root.right != null) stack.push(root.right);
            if(root.left != null) stack.push(root.left);
        }
        return res;
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(n)

  • Solution2 – recursive
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        helper(root, res);
        return res;
    }
    private void helper(TreeNode root, List<Integer> res) {
        if (root == null) return;
        res.add(root.val);
        helper(root.left, res);
        helper(root.right, res);
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(n)

Posted on In
Symbols count in article: 3k Reading time ≈ 3 mins.

正文

写下这篇文章是想说说我对专业与兴趣之间的关系的看法。当我们大学选专业的时候，当我们研究生选方向的时候，当我们博士选方向的时候，当我们工作选岗位的时候，都会很疑惑到底哪个方向更适合自己。询问了一堆前辈后，有的告诉你要根据前景选，有的告诉你要根据兴趣选，最后困扰我们的问题就变成了，到底是选一个自己感兴趣的方向还是选一个前景好的方向？这个问题就是本文主要想讨论的一个问题。

面对一个问题，我们先要来深入了解一下，这个问题的本质是什么。所以，我想先说说我对兴趣的看法。我对兴趣的看法始终都是：不要把兴趣看得多么崇高，你做的好你就感兴趣，你做的不好你就不感兴趣。

Read more »

Posted on In
Symbols count in article: 1.2k Reading time ≈ 1 mins.

正文

五年前。

小楼无聊的在床上刷着手机，不时发出阵阵笑声。

“大威天龙，世尊地藏，般若诸佛，般若巴嘛空。“

“三年之期已到！恭迎龙王√“

“生不出人，我很抱歉“

“人在美国，刚下飞机”

“。。。。。。”

“嗡嗡嗡”

Read more »

Posted on In
Symbols count in article: 1.6k Reading time ≈ 1 mins.

正文

轰隆隆, 飞机终于起飞了。下面的房屋越来越远，渐渐消失在视野中。

大痣一上飞机就闭上了眼睛，身体似乎还有些发抖。小楼在旁边看着大痣，嘴角露出了一丝坏笑。大痣虽然什么都看得都比小楼透彻，但就是害怕坐飞机。偏偏大痣每次都嘴硬的说自己完全不怕，只是感觉飞机的冷气开的太足了，自己是被冻的发抖。每每看到大痣这个样子，小楼总会很开心，虽然他什么都不如大痣，但至少在这一点他觉得自己终于胜过大痣了。

Read more »