Posted Updated LeetCode / Easya minute read (About 126 words)

145. Binary Tree Postorder Traversal

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

后序遍历。
先递归左子节点。
然后递归右子节点。
最后将当前节点加入数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<Integer> ans;
    public List<Integer> postorderTraversal(TreeNode root) {
        ans = new ArrayList();
        traversal(root);
        return ans;
    }
    
    private void traversal(TreeNode root){
        if (root == null){
            return;
        }
        traversal(root.left);
        traversal(root.right);
        ans.add(root.val);
        return;
    }
}
Posted Updated LeetCode / Easya minute read (About 126 words)

94. Binary Tree Inorder Traversal

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

中序遍历。
先递归左子节点。
然后将当前节点加入数组。
最后递归右子节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<Integer> ans;
    public List<Integer> inorderTraversal(TreeNode root) {
        ans = new ArrayList();
        traversal(root);
        return ans;
    }
    
    private void traversal(TreeNode root){
        if (root == null){
            return;
        }
        traversal(root.left);
        ans.add(root.val);
        traversal(root.right);
        return;
    }
}
Posted Updated LeetCode / Easya minute read (About 126 words)

144. Binary Tree Preorder Traversal

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

先序遍历。
先将当前节点加入数组。
然后递归左子节点。
最后递归右子节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<Integer> ans;
    public List<Integer> preorderTraversal(TreeNode root) {
        ans = new ArrayList();
        traversal(root);
        return ans;
    }
    
    private void traversal(TreeNode root){
        if (root == null){
            return;
        }
        ans.add(root.val);
        traversal(root.left);
        traversal(root.right);
        return;
    }
}
Posted Updated LeetCode / Easy / 复习2 minutes read (About 320 words)

232. Implement Queue using Stacks

问题
Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

  • void push(int x) Pushes element x to the back of the queue.

  • int pop() Removes the element from the front of the queue and returns it.

  • int peek() Returns the element at the front of the queue.

  • boolean empty() Returns true if the queue is empty, false otherwise.
    Notes:

  • You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.

  • Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack’s standard operations.

创建两个栈。
当入队列时，将元素压入第一个栈。
当出队列或进行其他操作时，如第二个栈为空，则将第一个栈的元素倒出到第二个栈。
此时第二个栈内的内容为顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class MyQueue {
    Stack<Integer> s1;
    Stack<Integer> s2;
        
    public MyQueue() {
        s1 = new Stack();
        s2 = new Stack();
    }
    
    public void push(int x) {
        s1.add(x);
    }
    
    public int pop() {
        if (s2.isEmpty()){
            while (!s1.isEmpty()){
                s2.add(s1.pop());
            }
            return s2.pop();
        }
        else{
            return s2.pop();
        }
        
    }
    
    public int peek() {
        if (s2.isEmpty()){
            while (!s1.isEmpty()){
                s2.add(s1.pop());
            }
            return s2.peek();
        }
        else{
            return s2.peek();
        }
    }
    
    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */
Posted Updated LeetCode / Easya minute read (About 176 words)

1260. Shift 2D Grid

问题
Given a 2D grid of size m x n and an integer k. You need to shift the grid k times.

In one shift operation:

Element at grid[i][j] moves to grid[i][j + 1].
Element at grid[i][n - 1] moves to grid[i + 1][0].
Element at grid[m - 1][n - 1] moves to grid[0][0].
Return the 2D grid after applying shift operation k times.

遍历整个数组，将索引值加上移动的次数，得到新的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public List<List<Integer>> shiftGrid(int[][] grid, int k) {
        List<List<Integer>> ans = new ArrayList<>();
        int row = grid.length;
        int col = grid[0].length;
        int size = row * col;
        Integer[][] mat = new Integer[row][col];
        
        for (int i = 0; i < size; i++){
            int j = i + k;
            if ( j > size - 1){
                j %= size;
            }
            int nr = j / col;
            int nc = j % col;
            int or = i / col;
            int oc = i % col;
            
            mat[nr][nc] = grid[or][oc];
        }
        
        for (int i = 0; i < row; i++){
            List<Integer> nums = Arrays.asList(mat[i]);
            ans.add(nums);
        }
        
        return ans;
    }
}
Follow

Recents

Archives

Links

×