Posted Updated LeetCode / Easy / 复习a minute read (About 216 words)

112. Path Sum

问题
Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

递归，如果当前节点为null则返回false。
计算并更新当前节点的值。
如果当前节点为叶节点，且当前节点的值等于target，则返回true。
递归左子节点和右子节点，返回两者的或运算。

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
/**
 * 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 {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        return hasPathSum(root,0,targetSum);
    }
    
    private boolean hasPathSum(TreeNode root, int parentVal, int target){
        if (root == null){return false;}
        root.val = root.val + parentVal;
        if (root.left == null && root.right == null && root.val == target){
            return true;
        }
        return ( hasPathSum(root.left, root.val, target) || hasPathSum(root.right, root.val, target));
    }
}
Posted Updated LeetCode / Medium2 minutes read (About 276 words)

701. Insert into a Binary Search Tree

问题
You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

Notice that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

如果root为空则将值直接添加到根节点。
辅助方法比较当前节点的值。
如当前值大于添加的值，则检测左子节点是否为空。
如不为空则递归左子节点。
如当前值小于添加的值，则检测右子节点是否为空。
如不为空则递归右子节点。

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
/**
 * 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 {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null){
            root = new TreeNode(val);
        }
        insert(root,val);
        return root;
    }
    
    private void insert(TreeNode root, int val){
        if (root.val < val){
            if (root.right == null){
                root.right = new TreeNode(val);
            }
            insert(root.right, val);
        }
        else if (root.val > val){
            if (root.left == null){
                root.left = new TreeNode(val);
            }
            insert(root.left, val);
        }
        return;
    }
}
Posted Updated LeetCode / Easya minute read (About 188 words)

700. Search in a Binary Search Tree

问题
You are given the root of a binary search tree (BST) and an integer val.

Find the node in the BST that the node’s value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

搜索二叉树。
递归，如果现有根节点为空则返回空。
如果根节点的值大于搜索值则搜索其左子节点。
如果根节点的值小于搜索值则搜索其左右节点。

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
/**
 * 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 {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null){
            return null;
        }
        else if (root.val < val){
            return searchBST(root.right,val);
        }
        else if (root.val > val){
            return searchBST(root.left,val);
        }
        else{
            return root;
        }
    }
}
Posted Updated LeetCode / Easya minute read (About 156 words)

226. Invert Binary Tree

问题
Given the root of a binary tree, invert the tree, and return its root.

翻转二叉树。
交换当前节点的左右子节点。
分别递归其左右子节点。
当当前节点的两个节点均为null时返回。

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
/**
 * 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 {
    public TreeNode invertTree(TreeNode root) {
        if (root == null){
            return root;
        }
        invert(root);
        return root;
    }
    
    private void invert(TreeNode root){
        if ( root.left == null && root.right == null){
            return;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        if ( root.left != null ){
            invert(root.left);
        }
        if ( root.right != null ){
            invert(root.right);
        }
    }
}
Posted Updated LeetCode / Easya minute read (About 187 words)

101. Symmetric Tree

问题
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

递归root1的左子节点和root2的右子节点以及root2的左子节点以及root1的右子节点。如两者不相等则返回false。
如果传入的两个数值有一个为null，则两者不相等时返回false。反之返回true。

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 {
    public boolean isSymmetric(TreeNode root) {
        return isSymmetric(root,root);
    }
    
    public boolean isSymmetric(TreeNode root1, TreeNode root2){
        if ( root1 == null || root2 == null ){
            if(root1 == root2){return true;}
            else{return false;}
        }
        if ( root1.val == root2.val ){
            return isSymmetric(root1.left,root2.right) && isSymmetric(root1.right,root2.left);
        }
        else{
            return false;
        }
    }
}
Posted Updated LeetCode / Easy / 复习a minute read (About 215 words)

104. Maximum Depth of Binary Tree

问题
Given the root of a binary tree, return its maximum depth.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

递归，每次返回左子节点和右子节点中较大的结果+1。
当节点为null时返回0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 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 {
    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }
}

BFS搜索，每次倾倒出队列里所有的元素并将level+1。
搜索完毕返回level。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        Queue<TreeNode> q = new LinkedList();
        q.offer(root);
        int level = 0;
        while(!q.isEmpty()){
            int size = q.size();
            for (int i = 0; i < size; i++){
                TreeNode curr = q.poll();
                if(curr.left!=null){q.offer(curr.left);}
                if(curr.right!=null){q.offer(curr.right);}
            }
            level++;
        }
        return level;
    }
}
Posted Updated LeetCode / Medium / 复习a minute read (About 183 words)

102. Binary Tree Level Order Traversal

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).

Solution

BFS搜索，层序遍历，记录每个层级的节点数量size。
在遍历时挤出size个节点，并将其子节点加入队列。

Code

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
/**
 * 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 {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) return ret;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);

        int size = 1;
        while(!q.isEmpty()){
            List<Integer> list = new ArrayList<>();
            TreeNode curr = null;
            for(int i = 0; i < size; i++){
                curr = q.poll();
                if(curr.left != null) q.offer(curr.left);
                if(curr.right != null) q.offer(curr.right);
                list.add(curr.val);
            }
            ret.add(list);
            size = q.size();
        }
        return ret;
    }
}
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 / Medium / 复习2 minutes read (About 361 words)

116. Populating Next Right Pointers in Each Node

问题
You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

1
2
3
4
5
6
 struct Node {
 int val;
 Node *left;
 Node *right;
 Node *next;
>}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

递归，当root为null时返回。
如果root有右节点，则左节点next指向右节点。
如果root有右节点同时next已经指向了一个节点，则将其右节点next指向该节点的左子节点。
递归左右子节点，并返回root。

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
/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        if (root==null){return root;}
        if (root.right!=null){
            root.left.next = root.right;
            if (root.next!=null){
                root.right.next = root.next.left;
            }
        }
        connect(root.left);
        connect(root.right);
        return root;
    }
}

BFS搜索每一个节点，将节点指向队列中next下一个节点。
当计数器达到2的指数时，将节点指向null。

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
class Solution {
    public Node connect(Node root) {
        if (root == null){
            return root;
        }
        
        int count = 1;
        Queue<Node> q = new LinkedList();
        q.offer(root);
        while (!q.isEmpty()){
            count++;
            Node curr = q.poll();
            if ( isPow(count) ){
                curr.next = null;
            }
            else{
                curr.next = q.peek();
            }
            if(curr.left!=null){
                q.add(curr.left);
            }
            if(curr.right!=null){
                q.add(curr.right);
            }

        }
        return root;
    }
    
    private boolean isPow(int val){
        if(val == 0 || val == 1){
            return false;
        }
        while ( val % 2 == 0 ){
            val = val / 2;
        }
        if (val == 1){
            return true;
        }
        return false;
    }
}
Posted Updated LeetCode / Easy / 复习a minute read (About 170 words)

20. Valid Parentheses

问题
Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.

用栈储存遍历中的字符。
如果是“（”，“{”或“[”，则入栈。
如果是其他字符，且不与栈顶的字符成对，则返回false。
其他情况需要pop掉栈顶。

  • toCharArray(): 将字符串转换为字符数组，便于遍历。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack();
        
        for (char c : s.toCharArray()){
            if ( c == '(' || c == '{' || c == '[' ){
                stack.push(c);
            }
            else if ( stack.size() == 0 || 
                     c == ')' && stack.peek() != '(' || 
                     c == '}' && stack.peek() != '{' || 
                     c == ']' && stack.peek() != '[') {
                return false;
            }
            else{
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
}
Posted Updated LeetCode / Easy / 复习2 minutes read (About 247 words)

617. Merge Two Binary Trees

问题
You are given two binary trees root1 and root2.

Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.

Return the merged tree.

Note: The merging process must start from the root nodes of both trees.

递归。将root1和root2合并到root1。
如果一个节点为null，则返回另一个节点。
否则root1的值为root1 + root2的值。
root1.left递归root1和root2的left。
root2.right递归root1和root2的right。
返回root1。

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
/**
 * 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 {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if( root1 == null ){
            return root2;
        }
        if( root2 == null ){
            return root1;
        }
        
        root1.val = root1.val + root2.val;
        root1.left = mergeTrees(root1.left,root2.left);
        root1.right = mergeTrees(root1.right,root2.right);
        
        return root1;
    }
}
Posted Updated LeetCode / Easya minute read (About 167 words)

83. Remove Duplicates from Sorted List

问题
Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

设置前一个节点和当前节点两个指针。
由于是有数的链表，遍历时可以直接比较两个节点。
如相等则前一个节点的next指向当前节点的next。

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        
        if ( head == null){
            return head;
        }
        if ( head.next == null){
            return head;
        }
        ListNode prev = head;
        ListNode curr = head.next;
        
        while(curr != null){
            if(prev.val != curr.val){
                curr = curr.next;
                prev = prev.next;
            }
            else{
                prev.next = curr.next;
                curr = curr.next;
            }
        }
        return head;
    }
}
Posted Updated LeetCode / Easy / 复习2 minutes read (About 268 words)

206. Reverse Linked List

问题
Given the head of a singly linked list, reverse the list, and return the reversed list.

翻转列表，当链表长度不足时，直接返回原链表。
将头元素设置到preNode，同时将其next设置为null，作为新链表的尾。
将其余的元素设置到curNode。

当当前节点不为null时
遍历：

  1. 将curNode的next保存在temp。
  2. 将curNode的next指向preNode，作为preNode的上一个节点。
  3. 将preNode指向curNode，完成交换。
  4. 将curNode指向temp，curNode变为原来的curNode的next。
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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        
        if( head == null ){   //if not enough, return head
            return head;
        }
        if ( head.next == null ){
            return head;
        }
        
        ListNode preNode = head;    //set head to preNode, it will be the last node in the end
        ListNode curNode = head.next;   //curNode move to next
        preNode.next = null;    //only preserve one head node
        ListNode temp;
        
        while( curNode != null ){
            temp = curNode.next;    //preserve nodes after curNode
            curNode.next = preNode; //cur -> pre
            preNode = curNode;  //set back reversed list to preNode
            curNode = temp; //put back preserved nodes, curNode move to the next
        }
        return preNode;
    }

}
Posted Updated LeetCode / Easy / 复习a minute read (About 217 words)

21. Merge Two Sorted Lists

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

先设置空的哨兵节点，然后将尾部指针指向这个节点。
遍历两个链表，将尾部节点的下一个值指向两个节点中值较小的一个。
然后将指针移动到下一个值。
最后返回哨兵节点的下一个节点。

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummyHead = new ListNode();
        ListNode tail = dummyHead;

        
        while ( list1 != null && list2 !=null ){
            if (list1.val < list2.val){
                tail.next = list1;
                list1 = list1.next;
                tail = tail.next;
            }
            else{
                tail.next = list2;
                list2 = list2.next;
                tail = tail.next;
            }
 
        }
        
        if ( list1 == null){
            tail.next = list2;
        }
        else {
            tail.next = list1;
        }
        
        return dummyHead.next;
    }
}
Posted Updated LeetCode / Easy / 复习a minute read (About 201 words)

141. Linked List Cycle

问题
Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

遍历并移动快慢指针。
如两个指针最终相遇，则链表中有循环。
如快指针移动到链表尾部，则链表无循环。

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 singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        if ( head == null){
            return false;
        }
        else if ( fast.next == null){
            return false;
        }
        
        while( fast != null && fast.next != null ){
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast){
                return true;
            }
        }
        return false;
    }
}

Follow

Recents

Archives

Links

×