7.10号刷题

发表于 | 分类于 | 0 comments

第一题 437. Path Sum III

题目描述

给定一颗二叉树，每个节点包含一个整数值。

计算所有和为给定值的路径个数。

路径不一定以根开始，也不一定以叶子结束，但是必须自上而下（从双亲结点到孩子节点）

树节点个数不超过1000，并且节点值的范围在-1,000,000到1,000,000之间。

算法

双回溯

由于需要遍历所有子树，因此采用双重回溯的办法，因此对所有子树的可能性进行遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class pathSum437 {
    public int pathSum(TreeNode root, int sum) {
        if (root == null) return 0;
        return helper(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }
    public int helper(TreeNode root, int sum) {
        if (root == null) return 0;
        int res = 0;
        if (root.val == sum) {
            res++;
        }
        res += helper(root.left, sum - root.val);
        res += helper(root.right, sum - root.val);
        return res;
    }
}

HashMap(PreSum)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public int pathSum(TreeNode root, int sum) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        return backtrack(root, 0, sum, map);
    }    
    public int backtrack(TreeNode root, int sum, int target, Map<Integer, Integer> map) {
        if (root == null) return 0;
        
        sum += root.val;
        int res = map.getOrDefault(sum - target, 0);
        map.put(sum, map.getOrDefault(sum, 0) + 1);
        res += backtrack(root.left, sum, target, map) + backtrack(root.right, sum, target, map);
        map.put(sum, map.get(sum) - 1);
        return res;        
    }
}

第二题 637. Average of Levels in Binary Tree

题目描述

输出每一层的平均值

算法

层次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class averageOfLevels637 {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            long size = queue.size(), sum = 0;
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
                sum += cur.val;
            }
            double tempRes = (double) sum / (double) size;
            res.add(tempRes);
        }
        return res;
    }
}

第三题 102. Binary Tree Level Order Traversal

题目描述

层次遍历一课树

算法

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

第四题 107. Binary Tree Level Order Traversal II

题目描述

从底层到上层，层次遍历一棵树

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> tempRes = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                if (cur.left != null) queue.add(cur.left);
                if (cur.right != null) queue.add(cur.right);
                tempRes.add(cur.val);
            }
            res.add(new ArrayList<>(tempRes));
        }
        Collections.reverse(res);
        return res;        
    }
}

第五题 449. Serialize and Deserialize BST

题目描述

序列化是指将数据结构或者对象转换为比特序列，使其可以保存在文件或者内存缓冲区中，也可以通过网络链路传输给本机或者其他计算机，在之后进行重构。

设计算法序列化/反序列化一棵二叉搜索树。对序列化/反序列化算法的具体实现没有限制。你需要确保一棵二叉树可以序列化成字符串，字符串可以反序列化为原始二叉树。

编码的字符串应该尽可能紧凑。

注意：不要使用类成员/全局变量/静态变量来保存状态。你的序列化/反序列化算法应该是无状态的

算法

算法最核心的地方是利用queue的特性，和BST的特性。利用队列，回溯的构建一个二叉搜索树

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
public class Codec {
    private static final String SEP = ",";
    private static final String NULL = "null";
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        if (root == null) return NULL;
        Stack<TreeNode> st = new Stack<>();
        st.push(root);
        while (!st.isEmpty()) {
            root = st.pop();
            sb.append(root.val).append(SEP);
            if (root.right != null) st.push(root.right);
            if (root.left != null) st.push(root.left);
        }
        return sb.toString();
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data.equals(NULL)) return null;
        String[] strs = data.split(SEP);
        Queue<Integer> queue = new LinkedList<>();
        for (String e : strs) {
            queue.offer(Integer.valueOf(e));
        }
        return getNode(queue);
    }
    public TreeNode getNode(Queue<Integer> queue) {
        if (queue.isEmpty()) return null;
        TreeNode root = new TreeNode(queue.poll());
        Queue<Integer> smaller = new LinkedList<>();
        while (!queue.isEmpty() && queue.peek() < root.val) {
            smaller.add(queue.poll());
        }
        root.left = getNode(smaller);
        root.right = getNode(queue);
        return root;
    }
}

第六题 173. Binary Search Tree Iterator

题目描述

实现一个二叉搜索树（BST）的迭代器。你的迭代器会使用BST的根节点初始化。

调用next()会返回BST中下一个最小的数字。

注意：next()和hasNext()应该满足平均O(1)时间复杂度和O(h)空间复杂度，其中h是树的高度

算法

利用stack，把个root的的所有左边节点推入stack中，然后进行pop操作，进行指向下一个节点的操作

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
public class BSTIterator {
    Stack<TreeNode> stack = new Stack<>();
    public BSTIterator(TreeNode root) {
        pushall(root);
    }
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stack.isEmpty();
    }
    /** @return the next smallest number */
    public int next() {
        TreeNode cur = stack.pop();
        pushall(cur.right);
        return cur.val;
    }
    
    public void pushall(TreeNode root) {
        while (root!= null) {
            stack.push(root);
            root = root.left;
        }
    }
}

第七题 285. Inorder Successor in BST

题目描述

找寻在中序遍历的情况下，在二叉搜索树中的下一个节点

算法

1
2
3
4
5
6
7
8
9
10
11
12
public class inorderSuccessor285 {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if (root == null) return null;
        if (root.val <= p.val) {
            return inorderSuccessor(root.right, p);
        } else {
            TreeNode left = inorderSuccessor(root.left, p);
            return left == null ? root : left;
        }
    }
}

第八题 145. Binary Tree Postorder Traversal

题目描述

后序遍历

算法

利用插入在第一个位置的特性，进行循环

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

第九题 270. Closest Binary Search Tree Value

题目描述

找到离target

算法

Recursive
1
2
3
4
5
6
7
8
9
10
public class Solution {
    public int closestValue(TreeNode root, double target) {
        int cur = root.val;
        TreeNode next = cur > target ? root.left : root.right;
        if (next == null) return cur;
        int nextC  = closestValue(next, target);
        return Math.abs(cur - target) > Math.abs(nextC - target) ? nextC : cur;        
    }
}
iterative
1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public int closestValue2(TreeNode root, double target) {
        int res = root.val;
        while (root != null) {
            if (Math.abs(res - target) > Math.abs(root.val - target)) {
                res = root.val;
            }
            root = root.val > target ? root.left : root.right;
        }
        return res;
    }
}