7.11号刷题

发表于 | 分类于 | 0 comments

第一题 272. Closest Binary Search Tree Value II

题目描述

在BST中找出k个距离target最近的点

算法

这题先用两个stack，利用中序遍历和反中序遍历，将值按照顺序存储好。然后分别按顺序弹出

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
public class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Stack<Integer> pre = new Stack<>();
        Stack<Integer> post = new Stack<>();
        
        preSuccessor(root, target, pre);
        postSuccessor(root, target, post);
        
        while (k-- > 0) {
            if (pre.isEmpty()) {
                res.add(post.pop());
            } else if (post.isEmpty()) {
                res.add(pre.pop());
            } else if (target - pre.peek() > post.peek() - target) {
                res.add(post.pop());
            } else {
                res.add(pre.pop());
            }
        }
        return res;
    }
    
    public void preSuccessor(TreeNode root, double target, Stack<Integer> stack) {
        if (root == null) return;
        preSuccessor(root.left, target, stack);
        if (root.val > target) return;
        stack.push(root.val);
        preSuccessor(root.right, target, stack);
    }
    
    public void postSuccessor(TreeNode root, double target, Stack<Integer> stack) {
        if (root == null) return;;
        postSuccessor(root.right, target, stack);
        if (root.val <= target) return;
        stack.push(root.val);
        postSuccessor(root.left, target, stack);
    }
}

第二题 235. Lowest Common Ancestor of a Binary Search Tree

题目描述

给定一棵二叉搜索树（BST），寻找BST中两个给定节点的最近公共祖先（LCA）。

根据维基百科对LCA的定义：“节点v与w的最近公共祖先是树T上同时拥有v与w作为后继的最低节点（我们允许将一个节点当做其本身的后继）”

例如，题目描述的样例中，节点2和8的最近公共祖先（LCA）是6。另一个例子，节点2和4的LCA是2，因为根据LCA的定义，一个节点可以是其本身的后继。

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class lowestCommonAncestor235 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        int rval = root.val, pval = p.val, qval = q.val;
        if ((rval > pval && rval < qval) || (rval < pval && rval > qval)) {
            return root;
        } else if (rval == pval || rval == qval) {
            return rval == pval ? p : q;
        } else if (rval > pval && rval > qval) {
            return lowestCommonAncestor(root.left, p, q);
        } else {
            return lowestCommonAncestor(root.right, p, q);
        }
    }
}

第三题 236. Lowest Common Ancestor of a Binary Tree

题目描述

给定一棵二叉树，寻找其中两个给定节点的最近公共祖先（LCA）。

根据维基百科对LCA的定义：“节点v与w的最近公共祖先是树T上同时拥有v与w作为后继的最低节点（我们允许将一个节点当做其本身的后继）”

例如，题目描述的样例中，节点5和1的最近公共祖先（LCA）是3。另一个例子，节点5和4的LCA是5，因为根据LCA的定义，一个节点可以是其本身的后继。

算法

只有两种情况，一种是p和q分别在两边，那么当前节点即为共同的ancester。另一种是一个节点在另一个下面，那么在上面那个节点即为共同的ancester。

我们通过后序遍历，查看左右能否找到需要的p和q，如果找到，那么当前节点即为ancester。不能的话然后找到的那一边

1
2
3
4
5
6
7
8
9
10
11
12
public class lowestCommonAncestor236 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) return root;
        return left == null ? right : left;
    }
}

第四题 101. Symmetric Tree

题目描述

查看一棵树是否是对称树

算法

利用回溯，挨个检查

1
2
3
4
5
6
7
8
9
10
11
12
public class isSymmetric {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return helper(root.left, root.right);
    }
    public boolean helper(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        return left.val == right.val && helper(left.left, right.right) && helper(left.right, right.left);
    }
}

第五题 98. Validate Binary Search Tree

题目描述

查看一棵树是否是合理的二差搜索树

算法

Recursive
1
2
3
4
5
6
7
8
9
10
11
12
    public boolean isValidBST(TreeNode root) {
        return helper(root, Long.MAX_VALUE, Long.MIN_VALUE);
    }
    public boolean helper(TreeNode root, long max, long min) {
        if (root == null) return true;
        if (root.val >= max || root.val <= min) return false;
        return helper(root.left, root.val, min) && helper(root.right, max, root.val);
    }
}
Iterative
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class isValidBST98 {
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (pre != null && root.val <= pre.val) return false;
            pre = root;
            root = root.right;
        }
        return true;
    }
}

第六题 501. Find Mode in Binary Search Tree

题目描述

给定一棵包含重复元素的二叉树。寻找其中的所有众数。

注意：二叉树可能包含多个众数，以任意顺序返回即可。

算法

如果想要O(1)的空间复杂度，那么我们需要遍历两次整个树，然后记录下有多少个数出现了最大次数。然后初始化结果并进行输出。

关键的思路在于，对于这种变形的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
public class findMode501 {
    int curValue;
    int modeNum = 0;
    int maxNum = 0;
    int curCount = 0;
    int[] res;
    public int[] findMode(TreeNode root) {
        inOrder(root);
        res = new int[modeNum];
        curCount = 0;
        modeNum = 0;
        inOrder(root);
        return res;
    }
    public void inOrder(TreeNode root) {
        if (root == null) return;
        inOrder(root.left);
        handleValue(root.val);
        inOrder(root.right);
    }
    public void handleValue(int value) {
        if (value != curValue) {
            curValue = value;
            curCount = 0;
        }
        curCount++;
        if (curCount > maxNum) {
            maxNum = curCount;
            modeNum = 1;
        } else if (curCount == maxNum){
            if (res != null) {
                res[modeNum] = value;
            }
            modeNum++;
        }
    }
}

第七题 103. Binary Tree Zigzag Level Order Traversal

题目描述

对一个二叉树进行z行按行输出

算法

层次遍历

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
public class zigzagLevelOrder103 {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean leftToright = true;
        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.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
                if (leftToright) tempRes.add(cur.val);
                else tempRes.add(0, cur.val);
            }
            leftToright = !leftToright;
            res.add(new ArrayList<>(tempRes));
        }
        return res;
    }
}

第八题 129. Sum Root to Leaf Numbers

题目描述

找到所有根到叶节点的和

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    int sum = 0;
    public int sumNumbers(TreeNode root) {
        if (root == null) return sum;
        helper(root, "");
        return sum;
    }
    
    public void helper(TreeNode root, String tempSum) {
        if (root.left == null && root.right == null) {
            tempSum += root.val;
            sum += Integer.valueOf(tempSum);
            return;
        }
        tempSum += root.val;
        if (root.left != null) helper(root.left, tempSum);
        if (root.right != null) helper(root.right, tempSum);
    }
}
1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    public int sumNumbers(TreeNode root) {
        return sumNumbers(root, 0);
    }
    
    public int sumNumbers(TreeNode root, int sum) {
        if (root == null) return 0;
        if (root.right == null && root.left == null) return sum * 10 + root.val;
        return sumNumbers(root.left, sum * 10 + root.val) + sumNumbers(root.right, sum * 10 + root.val);
    }
}

第九题 257. Binary Tree Paths

算法

遍历整课数，并将root到每一个leaf的路径进行输出

算法

1
2
3
4
5
6
7
8
9
10
11
12
public class binaryTreePaths257 {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> answer = new ArrayList<String>();
        if (root != null) searchBT(root, "", answer);
        return answer;
    }
    private void searchBT(TreeNode root, String path, List<String> answer) {
        if (root.left == null && root.right == null) answer.add(path + root.val);
        if (root.left != null) searchBT(root.left, path + root.val + "->", answer);
        if (root.right != null) searchBT(root.right, path + root.val + "->", answer);
    }
}