7.5号刷题

发表于 | 分类于 | 0 comments

第一题 366. Find Leaves of 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 Solution {
    public List<List<Integer>> findLeaves(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        helper(res, root);
        return res;
    }
    public int helper(List<List<Integer>> res, TreeNode root) {
        if (root == null) return -1;
        int leftDepth = helper(res, root.left);
        int rightDepth = helper(res, root.right);
        int depth = Math.max(leftDepth, rightDepth) + 1;
        if (depth == res.size()) {
            res.add(new ArrayList<>());
        }
        res.get(depth).add(root.val);
        root.left = null; root.right = null;
        return depth;
    }
}

第二题 515. Find Largest Value in Each Tree Row

题目描述

给定二叉树，返回其每一行的最大元素。

算法

BFS
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
public class largestValues515 {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Queue<Element> queue = new LinkedList<>();
        queue.add(new Element(0, root));
        int l = 0, max = root.val;
        while (!queue.isEmpty()) {
            Element e = queue.poll();
            if (l != e.layer) {
                res.add(max);
                l = e.layer;
                max = e.cur.val;
                if (e.cur.left != null) queue.add(new Element(l + 1, e.cur.left));
                if (e.cur.right != null) queue.add(new Element(l + 1,e.cur.right));
            } else {
                max = Math.max(e.cur.val, max);
                if (e.cur.left != null) queue.add(new Element(l + 1, e.cur.left));
                if (e.cur.right != null) queue.add(new Element(l + 1, e.cur.right));
            }
            if (queue.isEmpty()) res.add(max);
        }
        return res;
    }
    class Element{
        int layer;
        TreeNode cur;
        Element (int l, TreeNode cur) {
            this.layer = l;
            this.cur = cur;
        }
    }
}

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        helper(root, res, 0);
        return res;
    }
    public void helper(TreeNode root, List<Integer> res, int depth) {
        if (root == null) return;
        
        int val = root.val;
        if (depth == res.size()) {
            res.add(val);
        } else  {
            res.set(depth, Math.max(res.get(depth), val));
        }
        helper(root.left, res, depth + 1);
        helper(root.right, res, depth + 1);        
    }
}

第三题 538. Convert BST to Greater Tree

题目描述

给定一棵二叉查找树（BST），将其转化为“Greater Tree”，原始BST中的每一个节点都替换为不小于其本身的各节点的和。

算法

从右开始遍历节点，并计算现在总共的sum值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class convertBST538 {
    int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        helper(root);
        return root;
    }
    public void helper(TreeNode root) {
        if (root == null) return;
        helper(root.right);
        root.val += sum;
        sum = root.val;
        helper(root.left);
    }
}

第四题 104. Maximum Depth of Binary Tree

题目描述

求一棵树的最深的深度

算法

利用回溯的方法进行求取

1
2
3
4
5
6
7
8
9
10
11
public class maxDepth104 {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        int depth = Math.max(leftDepth, rightDepth) + 1;
        return depth;
    }
}

第五题 110. Balanced Binary Tree

题目描述

查看一棵树是不是平衡树

算法

与之前的题目相似

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class isBalanced110 {
    boolean tag = true;
    public boolean isBalanced(TreeNode root) {
        helper(root);
        return tag;
    }
    public int helper(TreeNode root) {
        if (root == null || !tag) return -1;
        int leftDepth = helper(root.left);
        int rightDepth = helper(root.right);
        if (Math.abs(leftDepth - rightDepth) > 1) tag = false;
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

学到的东西

关于java值传递： 链接

如果传入的是普通数据 -> 出来不会改变
如果传入的是数据类型 -> 传入的实际上是数据类型的地址，如果数据类型本身提供了对自身的改变，那么可以改变值。 如果没有，就不不会改变。

第六题 111. Minimum Depth of Binary Tree

题目描述

求到最近的叶节点的最短距离

算法

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 minDepth111 {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        int leftDepth, rightDepth;
        if (root.left == null && root.right == null) {
            return 1;
        } else if (root.right == null) {
            return minDepth(root.left) + 1;
        } else if (root.left == null) {
            return minDepth(root.right) + 1;
        } else {
            leftDepth = minDepth(root.left);
            rightDepth = minDepth(root.right);
            return Math.min(leftDepth, rightDepth) + 1;
        }
    }
    
    //Refectory
    public int minDepthRe(TreeNode root) {
        if (root == null) return 0;
        int leftDepth = minDepthRe(root.left);
        int rightDepth = minDepthRe(root.right);
        return (leftDepth == 0 || rightDepth == 0) ? rightDepth + leftDepth + 1 : Math.min(rightDepth, leftDepth) + 1;
    }
}

第七题 226. Invert Binary Tree

题目描述

反转一棵树

算法

BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        
        Queue<TreeNode> pq = new LinkedList<>();
        pq.add(root);
        
        while (!pq.isEmpty()) {
            TreeNode cur = pq.poll();
            
            TreeNode temp = cur.left;
            cur.left = cur.right;
            cur.right = temp;
            
            if (cur.left != null) pq.add(cur.left);
            if (cur.right != null) pq.add(cur.right);
        }
        return root;        
    }
}
DFS
1
2
3
4
5
6
7
8
9
public class invertTree226 {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode cur = new TreeNode(root.val);
        cur.left = invertTree(root.right);
        cur.right = invertTree(root.left);
        return cur;
    }
}

第八题 582. Kill Process

题目描述

给定n个进程，进程ID为PID，父进程ID为PPID。

当杀死一个进程时，其子进程也会被杀死。

给定进程列表和其对应的父进程列表，以及被杀死的进程ID，求所有被杀死的进程ID。

注意：

  1. 给定被杀死的进程ID一定在进程列表之中
  2. n >= 1

算法

先用hashmap找出一个节点所有的孩子，再进行检查和删除。

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<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < ppid.size(); i++) {
            map.putIfAbsent(ppid.get(i), new ArrayList<>());
            map.get(ppid.get(i)).add(pid.get(i));
        }
        List<Integer> res = new ArrayList<>();
        Queue<Integer> pq = new LinkedList<>();
        pq.offer(kill);
        while (!pq.isEmpty()) {
            int cur = pq.poll();
            res.add(cur);
            if (map.containsKey(cur)) {
                pq.addAll(map.get(cur));
            }
        }
        return res;        
    }
}

第九题 563. Binary Tree Tilt

题目描述

给定二叉树，计算二叉树的“倾斜值”（tilt）

二叉树节点的倾斜值是指其左右子树和的差的绝对值。空节点的倾斜值为0。

注意：

  1. 节点和不超过32位整数范围
  2. 倾斜值不超过32位整数范围

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class findTilt563 {
    int sum = 0;
    public int findTilt(TreeNode root) {
        helper(root);
        return sum;
    }
    public int helper(TreeNode root) {
        if (root == null) return 0;
        int leftNum = helper(root.left);
        int rightNum = helper(root.right);
        System.out.println(leftNum + " " + rightNum);
        sum += Math.abs(leftNum - rightNum);
        return leftNum + rightNum + root.val;
    }
}

第十题 623. Add One Row to Tree

题目描述

给定二叉树，根节点为第1层，在其第d层追加一行值为v的节点。将第d层各左孩子节点链接为新节点的左孩子，各右孩子节点链接为新节点的右孩子。

若d为1，则将原来的根节点链接为新节点的左孩子。

算法

DFS
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
public class addOneRow623 {
    public TreeNode addOneRow(TreeNode root, int v, int d) {
        if (d == 1) {
            TreeNode cur = new TreeNode(v);
            cur.left = root;
            return cur;
        }
        helper(root, v, d, 1);
        return root;
    }
    public void helper(TreeNode root, int v, int d, int depNow) {
        if (root == null) return;
        if (depNow == d - 1) {
            TreeNode curLeft = new TreeNode(v);
            curLeft.left = root.left;
            root.left = curLeft;
            TreeNode curRight = new TreeNode(v);
            curRight.right = root.right;
            root.right = curRight;
            return;
        }
        helper(root.left, v, d, depNow + 1);
        helper(root.right, v, d, depNow + 1);
    }
}
BFS
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
public class Solution {
    public TreeNode addOneRow(TreeNode root, int v, int d) {
        if (d == 1) {
            TreeNode newroot = new TreeNode(v);
            newroot.left = root;
            return newroot;
        }
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        for (int i = 0; i < d - 2; i++) {
            int size = queue.size();
            for (int j = 0; j < size; j++) {
                TreeNode temp = queue.poll();
                if (temp.left != null) queue.add(temp.left);
                if (temp.right != null) queue.add(temp.right);
            }
        }
        
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            TreeNode curLeft = new TreeNode(v);
            curLeft.left = cur.left;
            cur.left = curLeft;
            
            TreeNode curRight = new TreeNode(v);
            curRight.right = cur.right;
            cur.right = curRight;
        }
        return root;        
    }
}

第十一题 404. Sum of Left Leaves

题目描述

给定二叉树，计算其所有左叶子的和。

算法

BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;
        
        int res = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur.left != null && cur.left.left == null && cur.left.right == null) res += cur.left.val;
            if (cur.left != null) queue.add(cur.left);
            if (cur.right != null) queue.add(cur.right);
        }
        return res;        
    }
}
DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class sumOfLeftLeaves404 {
    int sum = 0;
    public int sumOfLeftLeaves(TreeNode root) {
        helper(root, false);
        return sum;
    }
    public void helper(TreeNode root, boolean tag) {
        if (root == null) return;
        if (root.left == null && root.right == null && tag) {
            sum += root.val;
            return;
        }
        helper(root.left, true);
        helper(root.right, false);
    }
}

第十二题 100. Same Tree

题目描述

给定两棵二叉树，编写函数检查它们是否相等。

当且仅当两棵二叉树的结构相同并且节点值也相同时，判定为相等。

算法

1
2
3
4
5
6
7
8
public class isSameTree100 {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null || q == null) return p == q;
        if (p.val != q.val) return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

第十三题 144. Binary Tree Preorder Traversal

题目描述

给定一棵二叉树，返回节点值的先序遍历结果（尽量使用非递归算法）。

算法

自己的(比较傻)
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
public class preorderTraversal144 {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode cur;
        boolean tag = true;
        while (!stack.isEmpty()) {
            if (tag) {
                cur = stack.peek();
                res.add(cur.val);
                while (cur.left != null) {
                    cur = cur.left;
                    stack.push(cur);
                    res.add(cur.val);
                }
                stack.push(cur);
                res.add(cur.val);
                System.out.println(res);
                tag = false;
            } else {
                cur = stack.pop();
                if (cur.right != null) {
                    stack.push(cur.right);
                    tag = true;
                }
            }
        }
        return res;
    }
}
别人的

先将右边的几点全部推入stack中，在进行挨个遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        Stack<TreeNode> rights = new Stack<>();
        
        while (root != null) {
            res.add(root.val);
            if (root.right != null) rights.push(root.right);
            root = root.left;
            if (root == null && !rights.isEmpty()) {
                root = rights.pop();
            }
        }
        return res;        
    }
}

第十四题 255. Verify Preorder Sequence in Binary Search Tree

题目描述

查看一个数组能否正确的组成一课排序树

算法

利用stack，在进入每个右边节点的时候，查看右边节点中的所有节点是否都小于部分根节点

Stack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class verifyPreorder255 {
    public boolean verifyPreorder(int[] preorder) {
        int min = Integer.MIN_VALUE;
        Stack<Integer> stack = new Stack<>();
        for (int num : preorder) {
            if (num < min) return false;
            while (!stack.isEmpty() && num > stack.peek()) {
                min = stack.pop();
            }
            stack.push(num);
        }
        return true;
    }
}
Array
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
public class verifyPreorder255 {
    public boolean verifyPreorder(int[] preorder) {
        int min = Integer.MIN_VALUE;
        Stack<Integer> stack = new Stack<>();
        for (int num : preorder) {
            if (num < min) return false;
            while (!stack.isEmpty() && num > stack.peek()) {
                min = stack.pop();
            }
            stack.push(num);
        }
        return true;
    }
    public boolean verifyPreorder2(int[] preorder) {
        int low = Integer.MIN_VALUE, i = -1;
        for (int p : preorder) {
            if (p < low)
                return false;
            while (i >= 0 && p > preorder[i])
            {
                low = preorder[i--];
            }
            preorder[++i] = p;
        }
        return true;
    }
}

第十五题 230. Kth Smallest Element in a BST

题目描述

给定一棵二叉搜索树（BST），编写一个函数kthSmallest找出其中第k小的元素。

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class kthSmallest230 {
    int count = 0;
    int number = 0;
    public int kthSmallest(TreeNode root, int k) {
        count = k;
        helper(root);
        return number;
    }
    public void helper(TreeNode root) {
        if (root.left != null) helper(root.left);
        count--;
        if (count == 0) {
            number = root.val;
            return;
        }
        if (root.right != null) helper(root.right);
    }
}