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 / 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 / 复习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 / Easy / 复习2 minutes read (About 246 words)

733. Flood Fill

答案
An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image.

You are also given three integers sr, sc, and newColor. You should perform a flood fill on the image starting from the pixel image[sr][sc].

To perform a flood fill, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with newColor.

Return the modified image after performing the flood fill.

深度优先搜索。
如果当前像素颜色等于最初的颜色，则变更为新颜色。
然后继续递归四个周围的像素。

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 int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int oldColor = image[sr][sc];
        if (oldColor != newColor){
            dfs(image,sr,sc,oldColor,newColor);
        }

        return image;
    }
    
    private void dfs(int[][] image, int r, int c, int oldColor, int newColor){
        if (image[r][c] == oldColor){
            image[r][c] = newColor;
            
            if (r>=1){
                dfs(image,r-1,c,oldColor,newColor);
            }
            if (c>=1){
                dfs(image,r,c-1,oldColor,newColor);
            }
            if (r<image.length-1){
                dfs(image,r+1,c,oldColor,newColor);
            }
            if (c<image[0].length-1){
                dfs(image,r,c+1,oldColor,newColor);
            }
        }
    }
}
Follow

Recents

Archives

Links

×