606. Construct String from Binary Tree
Posted Updated LeetCode / Easy2 minutes read (About 277 words)

606. Construct String from Binary Tree

Question

Given the root of a binary tree, construct a string consisting of parenthesis and integers from a binary tree with the preorder traversal way, and return it.

Omit all the empty parenthesis pairs that do not affect the one-to-one mapping relationship between the string and the original binary tree.

Solution

DFS搜索，先序遍历到每个节点将其加入StringBuffer。
如果当前节点有左子节点或右子节点，则递归左子节点，并在前后添加一对括号。（如果有右子节点的情况即使左子节点为空也需要添加一对括号加以区别。）
如果当前节点有右子节点，则递归右子节点，并在前后添加一对括号。

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 {
    StringBuffer sb;
    public String tree2str(TreeNode root) {
        sb = new StringBuffer();
        dfs(root);
        return sb.toString();
    }
    
    private void dfs(TreeNode root){
        if(root == null) return;
        sb.append(root.val);
        
        boolean hasLeft = root.left != null, hasRight = root.right != null;
        
        if(hasLeft || hasRight) sb.append("(");
        dfs(root.left);
        if(hasLeft || hasRight) sb.append(")");
        
        if(hasRight) sb.append("(");
        dfs(root.right);
        if(hasRight) sb.append(")");
    }
}
814. Binary Tree Pruning
Posted Updated LeetCode / Medium3 minutes read (About 387 words)

814. Binary Tree Pruning

Question

Given the root of a binary tree, return the same tree where every subtree (of the given tree) not containing a 1 has been removed.

A subtree of a node node is node plus every node that is a descendant of node.

Solution 1

DFS搜索，首先递归两个子节点。
在搜索时如果节点为0且两个子节点均为null，则返回null。否则返回节点本身。

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
/**
 * 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 pruneTree(TreeNode root) {
        if(root == null) return null;
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        if(root.left == null && root.right == null && root.val == 0) return null;
        else return root;
    }
}

Solution 2

DFS搜索，返回子节点和自己中是否包含1。
如果节点为null，则返回false。
如果自己为1，则返回true。
否则返回两个子节点中是否有true。

BFS搜索，根据每个节点的子节点是否包含1来决定左右子节点是否保存。
如果没有1，则将对应的子节点修改为null。

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
/**
 * 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 pruneTree(TreeNode root) {
        if(!hasOne(root)) return null;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            TreeNode curr = q.poll();
            if(hasOne(curr.left)) q.add(curr.left);
            else curr.left = null;
            if(hasOne(curr.right)) q.add(curr.right);
            else curr.right = null;
        }
        return root;
    }
    
    private boolean hasOne(TreeNode root){
        if(root == null) return false;
        if(root.val == 1) return true;
        else return hasOne(root.left) || hasOne(root.right);
    }
}
429. N-ary Tree Level Order Traversal
Posted Updated LeetCode / Mediuma minute read (About 204 words)

429. N-ary Tree Level Order Traversal

Question

Given an n-ary tree, return the level order traversal of its nodes’ values.

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

Solution

BFS搜索，层序遍历。
用level记录上一层的个数。
当队列不为空时，每次挤出level个节点，并将其子节点加入队列。
将当前层次的节点值加入列表。
最后更新level的数量。

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
39
40
41
42
/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

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

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) return res;
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        int level = 1;
        
        while(!q.isEmpty()){
            List<Integer> arr = new ArrayList<>();
            for(int i = 0; i < level; i++){
                Node curr = q.poll();
                for(Node child : curr.children){
                    q.offer(child);
                }
                arr.add(curr.val);
            }
            res.add(arr);
            level = q.size();
        }
        return res;
    }
}
967. Numbers With Same Consecutive Differences
Posted Updated LeetCode / Medium2 minutes read (About 228 words)

967. Numbers With Same Consecutive Differences

Question

Return all non-negative integers of length n such that the absolute difference between every two consecutive digits is k.

Note that every number in the answer must not have leading zeros. For example, 01 has one leading zero and is invalid.

You may return the answer in any order.

Solution

回溯，每次传入上一个数字和剩余的位数。
全局变量sum记录加和。
DFS搜索，每次计算下一位的可行数字并递归。
用回溯维护sum的值。
如果剩余位数为1，则将当前的sum加入结果，并清零sum。

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
39
40
41
42
43
class Solution {
    List<Integer> res;
    int sum;
    public int[] numsSameConsecDiff(int n, int k) {
        res = new ArrayList<>();
        for(int i = 1; i < 10; i++){
            sum = 0;
            dfs(i, n, k);
        }
        
        int[] ret = new int[res.size()];
        for(int i = 0; i < res.size(); i++){
            ret[i] = res.get(i);
        }
        return ret;
    }
    
    private void dfs(int prev, int n, int k){
        sum += prev;
        if(n == 1){
            res.add(sum);
            return;
        }
        
        if(k == 0){
            sum *= 10;
            dfs(prev + k, n-1, k);
            sum /= 10;
            return;
        }
        if(prev + k < 10){
            sum *= 10;
            dfs(prev + k, n-1, k);
            sum /= 10;
        }
        if(prev >= k){
            sum *= 10;
            dfs(prev - k, n-1, k);
            sum /= 10;
        }
    }
}

637. Average of Levels in Binary Tree
Posted Updated LeetCode / Esaya minute read (About 209 words)

637. Average of Levels in Binary Tree

Question

Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10<sup>-5</sup> of the actual answer will be accepted.

Solution

BFS搜索，记录单层的总和sum和单层的个数count。
每次遍历一个层级的所有节点，并更新sum和count。
遍历完毕后将当层级的平均数加入列表，同时将sum和count清零。

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
39
40
41
/**
 * 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<Double> averageOfLevels(TreeNode root) {
        List<Double> res = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        
        double sum = 0, count = 0;
        int level = 1;
        q.add(root);
        
        while(!q.isEmpty()){
    
            for(int i = 0; i < level; i++){
                TreeNode curr = q.poll();
                if(curr.left != null) q.add(curr.left);
                if(curr.right != null) q.add(curr.right);
                count++;
                sum += curr.val;
            }
            res.add(sum/count);
            sum = 0;
            count = 0;
            level = q.size();
        }
        return res;
    }
}
Follow

Recents

Archives

Links

×