CC's Boat

一顾青山舟远去，归来仍是顾青山

0%

Posted on

LeetCode 235.二叉搜索树的最近公共祖先

本题相较于非BST的LCA求解要容易得多，因为每次递归时我们可以利用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
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
        // if root.val == q.val or p.val then no need to traverse
        if (root == null || root.val == q.val || root.val == p.val) {
            return root;
        }

        // if both q's and p's val are less than root.val then search the left side
        if (root.val > q.val && root.val > p.val) {
            return lowestCommonAncestor(root.left, p, q);
        }

        // if both q's and p's val are larger than root.val then search the right side
        if (root.val < q.val && root.val < p.val) {
            return lowestCommonAncestor(root.right, p, q);
        }

        // else it means that the two nodes are in both sides, no matter q is in left &&
        // p in the right or the reversed situation, just return root 
        return root;


    }
}

LeetCode 701. 二叉搜索树中的插入操作

二叉搜索树的插入操作还是相对简单的，找到目标位置，插入即可，不涉及树结构的改变。

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
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {

        if (root == null) {
            root = new TreeNode (val);
        }else {
            insertRecursively(root, val);
        }

        return root;
    }

    // a helper function help us do the recursion 
    private void insertRecursively (TreeNode node, int val) {
       
        if (node == null) {
            return;
        }

        if (val < node.val) {
           if (node.left != null) {
            insertNode(node.left, val);
           }else {
            node.left = new TreeNode (val);
           }
        }

        if (val > node.val) {
            if (node.right != null) {
             insertNode(node.right, val);
            }else {
             node.right = new TreeNode (val);
            }
         }

    }
}

LeetCode 450. 删除二叉搜索树中的节点

这道题还是挺有难度的，需要考虑很多种情况，主要是因为删除节点会对树的结构带来改变。

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
44
45
46
47
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {

        if (root == null) {
            return root;
        }
        List<Integer> list = new LinkedList<>();

        // if root is the node to delete
        if (root.val == key) {

            // if right branch is null then return left
            if (root.left != null && root.right == null) {
                return root.left;
            }

            // if left branch is null then return right
            if (root.left == null && root.right != null) {
                return root.right;
            }

            // if no children just return null
            if (root.left == null && root.right == null) {
                return null;
            }

            // else: it means that both child nodes exist
            
            // find the leftmost child of root's right branch
            TreeNode node = root.right;
            while (node.left != null) {
                node = node.left;
            }
            node.left = root.left; 
            return root.right;

        }else {
            if (root.val > key) {
                // we maintain that deleteNode returns the new node after deletion
                root.left = deleteNode(root.left, key);
            }else {
                root.right = deleteNode(root.right, key);
            }
        }
        return root;
    }
}

Posted on

LeetCode 530.二叉搜索树的最小绝对差

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
class Solution {
    TreeNode prev = null;
    int minGap = Integer.MAX_VALUE;

    public int getMinimumDifference(TreeNode root) {
        getMD(root);
        return minGap;
    }


    public void getMD (TreeNode root) {
        
        if (root == null) {
            return;
        }

        // left
        getMD(root.left);

        // root
        if (prev != null) {

            // actually, no need to use abs, as this is a BST, 
            // the value of the node behind should be larger than its former element
            // int gap = Math.abs(root.val - prev.val);
            // int gap = root.val - prev.val;
            // if (gap < minGap) {
            //     minGap = gap;;
            // }

            minGap = Math.min(minGap, root.val - prev.val);
        }
        prev = root;

        // right
        getMD(root.right);
    }
}

事实上二叉搜索树中序遍历就是一个单调不减的数组, 想清楚这一点就好解决了，双指针操作，寻找有序数组最大差值。

LeetCode 501.二叉搜索树中的众数

如果这是一颗普通二叉树，那么它的中序遍历就无法被视为一个单调序列，那么就无法使用双指针法解决了，就得老老实实地使用任何一种方式遍历二叉树，统计各个元素出现的次数，用map存储，然后按照map的value进行排序，取出现频次最高的元素，比较麻烦。 但好在我们的目标是二叉搜索树。

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
44
45
46
47
class Solution {

    // 1 1 2 2 2 2 3 4 5 6 7 8 9 9 9 9 9
    private TreeNode prev;
    private int highestFrequence = 0;
    private int tempCount = 0;
    private List<Integer> ans = new LinkedList();
    
    public int[] findMode(TreeNode root) {
        inorder(root);
        int[] modes = ans.stream().mapToInt(i->i).toArray();
        return modes;
    }

    private void inorder(TreeNode cur) {

        if (cur == null) {
            return;
        }

        inorder(cur.left);

        // Step 1: update the tempCount
        if (prev == null) {
            tempCount = 1;
        }else if (prev.val == cur.val){
            tempCount++;
        }else {
            tempCount = 1;
        }

        // Step 2: update the ans list if necessary
        if (tempCount == highestFrequence) {
            ans.add(cur.val);
        }else if (tempCount > highestFrequence) {
          	// note here, if higher frequence exists, then drop all the current cached res
            highestFrequence = tempCount;
            ans.clear();
            ans.add(cur.val);
        }

        // Step 3: update the prev pointer
        prev = cur;

        inorder(cur.right);
    }
}

LeetCode 235.二叉树的最近公共祖先

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
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        if(root == null || root.val == p.val || root.val == q.val){
            return root;
        }

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        // as a root node of any sub-tree, is my left branch and my right branck both 
        // do not contain the target nodes, then I would definitely not be the LCA
        if(left == null && right == null) {
            return null;
            // similarly, if both my sub-tree contain the target, then because we
            // are backtracking, myself must be the LCA
        }else if (left != null && right != null) {
            return root;

            // if left does not contain target nodes, then the ans must be in the rightside
        }else if (left == null && right != null) {
            return right;
        }else {
            // the same with the leftside
            return left;
        }
    }
}

Posted on

LeetCode 654.最大二叉树

思路并不复杂， 和105，106有相似之处

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
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return counstructMyTree(nums, 0, nums.length);
    }

    private TreeNode counstructMyTree(int[] nums, int startIndex, int endIndex) {
        
        // exitrance
        if (startIndex >= endIndex) {
            return null;
        }

        int maxValue = -1;
        int maxIndex = -1;

        for (int i = startIndex; i < endIndex; i++) {

            if (nums[i] > maxValue){
                maxIndex = i;
                maxValue = nums[i];
            }
        }

        TreeNode root = new TreeNode (maxValue);

        // left branch
        root.left = counstructMyTree(nums, startIndex, maxIndex);

        // right branch
        root.right = counstructMyTree(nums, maxIndex + 1, endIndex);

        return root;
    }
}

LeetCode.617 合并二叉树

这道题一开始想复杂了，主要是一开始没想明白递归出口。其实结束递归的条件很清晰，如果一个树为空，那么剩下的分支则无需继续处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        
        // recursion exitrance
        if (root1 == null) return root2;
        if (root2 == null) return root1;

        root1.val += root2.val;

        root1.left = mergeTrees(root1.left, root2.left);
        root1.right = mergeTrees(root1.right, root2.right);

        return root1;

    }
}

LeetCode. 700 二叉搜索树中的搜索

简单题，目的是熟悉二叉搜索树的性质，一颗二叉搜索树的inorder表达一定是单调的。

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
class Solution {
    public TreeNode searchBSTRecursively(TreeNode root, int val) {
        if (root == null) return null;

        if (root.val == val) {
            return root;
        }else if (val > root.val) { 
            return searchBST(root.right, val);
        }else {
            return searchBST(root.left, val);
        }
    }

    public TreeNode searchBST(TreeNode root, int val) {
       
        while(root != null) {
            if(root.val == val) {
                return root;
            }else if (root.val < val) {
                root = root.right;
            }else {
                root = root.left;
            }
        }
        return null;
    }

LeetCode 98.验证二叉搜索树

如700所见，一颗树是否为二叉搜索树可以直观的从其中序遍历中体现，这一题便是这一个性质最好的诠释。

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
class Solution {

    private TreeNode prev;

    public boolean isValidBST(TreeNode root) {

        // when there is no node left, it's also regarded as valid BST
        if (root == null) {
            return true;
        }
        
        boolean isLeftValid = isValidBST(root.left);


        if (prev != null && prev.val >= root.val) {
            return false;
        }

        prev = root;


        boolean isRightValid = isValidBST(root.right);

        return isLeftValid && isRightValid;
    }
}

Posted on Edited on

LeetCode 513.找到树最左下角的值

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
class Solution {
    public int findBottomLeftValue(TreeNode root) {

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        TreeNode node = root;
        List<List<Integer>> ans = new LinkedList<>();

        while (!queue.isEmpty()) {
            int size = queue.size();

            List<Integer> values = new LinkedList<>();
            for (int i = 0; i < size; i++) {
                node = queue.poll();
                values.add(node.val);

                if (node.left != null) {
                    queue.add(node.left);
                }

                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            ans.add(values);
        }
        List<Integer> lastLevel = ans.get(ans.size() - 1);
        return lastLevel.get(0);
    }
}

层序遍历的思路很简单，找到所有层的value list， 返回最后一层最左侧元素.

LeetCode 112. 路经总和

因为题目只要求一个布尔的结果，即这样的路径是否存在，所以不需要考虑回溯的事情

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }

        if (root.val == targetSum && root.left == null && root.right == null) {
            return true;
        }

        return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
    }
}

LeetCode 113.路经总和-ii

因为题目要求返回所有可能的路径，在前一题代码的基础上进行少许修改，加入backtrack即可

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
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> ans = new LinkedList<>();
        preorder(ans, new LinkedList<>(), root, targetSum);
        return ans;
    }

    private void preorder (List<List<Integer>> ans, List<Integer> path, TreeNode node, int targetSum){
        
        // exitrance
        if (node == null) {
            return;
        }

        // add the val of the node into path
        path.add(node.val);

        // if this is a leaf node and its val is equals to target, record this path
        if (node.val == targetSum && node.left == null && node.right == null) {
          	// note here, we cannot directly add path list to the ans, as it is just
            // a temp container and would be changed during next track
            List<Integer> validPath = new LinkedList<>();
            validPath.addAll(path);
            ans.add(validPath);
        }

        // if there are children nodes, recursivelly call this func
        if (node.left != null) {
            preorder(ans, path, node.left, targetSum - node.val);
            // backtrack
            path.remove(path.size() - 1);
        }

        if (node.right != null) {
            preorder(ans, path, node.right, targetSum - node.val);
            // backtrack
            path.remove(path.size() - 1);
        }
    }
}

LeetCode 105.从前序和中序遍历序列构造二叉树

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
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildmyThree(preorder, 0, preorder.length, inorder, 0, inorder.length);
    }

    public TreeNode buildmyThree(int[] preorder, int preBeginIndex, int preEndIndex, int[] inorder, int inBeginIndex, int inEndIndex) {
        
        // when [preBeginIndex, preEndIndex) has no element, return null;
        if (preBeginIndex >= preEndIndex) {
                return null;
        }

        int rootValue = preorder[preBeginIndex];
        TreeNode root = new TreeNode(rootValue);

        // left branch
        // the key here is how to make sure the next range of preorder array and inorder array
        // deal with the inorder array first, as we know where to devide it into two partitions
        int devideInorderIndex = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == rootValue) {
                devideInorderIndex = i;
                break;
            }
        }

        // culculate the leftTreeSize to handle the preOrder array starting Index and size
        int leftTreeSize = devideInorderIndex - inBeginIndex;

        TreeNode leftNode = buildmyThree(preorder, preBeginIndex + 1, preBeginIndex + leftTreeSize + 1, inorder, inBeginIndex, devideInorderIndex);
        root.left = leftNode;

        // right branch
        TreeNode rightNode = buildmyThree(preorder, preBeginIndex + leftTreeSize + 1, preEndIndex, inorder, devideInorderIndex + 1, inEndIndex);
        root.right = rightNode;

        return root;
    }
}

LeetCode 106.从中序和后序遍历构造二叉树

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
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return buildmyTree(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }

    private TreeNode buildmyTree(int[] inorder, int inStartIndex, int inEndIndex, int[]postorder, int postStartIndex, int postEndIndex) {
        
        // if there is no elements in [inStartIndex, inEndIndex) then return
        if (inStartIndex >= inEndIndex) {
            return null;
        }

        // the last element in postorder is the root of the whole tree
        int rootValue = postorder[postEndIndex - 1];

        TreeNode root = new TreeNode(rootValue);

        // find the index of rootValue in inorder array to divide the inOrder array into two partitions

        int rootValueIndexAtInOrder = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == rootValue) {
                rootValueIndexAtInOrder = i;
                break;
            }
        }

        int leftPostOrderArraySize = rootValueIndexAtInOrder - inStartIndex;

        // the next step is recursively call this function to get the left node and right node
        root.left = buildmyTree( inorder, inStartIndex,  rootValueIndexAtInOrder, postorder, postStartIndex, postStartIndex + leftPostOrderArraySize);

        root.right = buildmyTree( inorder, rootValueIndexAtInOrder + 1, inEndIndex, postorder, postStartIndex + leftPostOrderArraySize, postEndIndex - 1);

        return root;
    }
}

这两道题其实有异曲同工之妙，其核心在于，仔细观察一颗二叉树的前，中和后序遍历会发现，前序遍历的首个元素是整个二叉树的root，后续遍历的最后一个元素是二叉树的root，由此就知道该怎么进一步对中序遍历的数组进行划分然后递归的解决子问题。 注意，在递归中维持不变量.

Posted on

LeetCode 110. 平衡二叉树

思路并不复杂，如果当前节点是平衡的，那么判断子节点是否平衡

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean isBalanced(TreeNode root) {

        if (root == null) {
            return true;
        }

        if (Math.abs(getHeight(root.left) - getHeight(root.right)) <= 1) {
            return isBalanced(root.left) && isBalanced(root.right);
        }else {
            return false;
        }
    }

    private int getHeight (TreeNode root) {
        if (root == null) {
            return -1;
        }
        return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
    }
}

LeetCode 257.二叉树的所有路径

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
44
45
46
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> ans = new LinkedList();
        
        if (root != null) {
            traversal(root, new LinkedList<Integer>(), ans);
        }

        return ans;
    }

    private void traversal (TreeNode node, List<Integer> path, List<String> ans) {
        
        // add the value of this node
        path.add(node.val);

        // if this node is a leaf node, convert the Integer list to String
        // and record it in ans
        if (node.left == null && node.right == null) {

            StringBuilder sb = new StringBuilder();

            for (int i = 0; i < path.size() - 1; i++) {
                sb.append(String.valueOf(path.get(i)));
                sb.append("->");
            }

            sb.append(path.get(path.size() - 1));
            ans.add(new String(sb));

            return;
        }

        // if there is child node, recursively call this func
        if (node.left != null) {
            traversal(node.left, path, ans);
            // note here, we need to BACKTRACK the path list after we checked this path
            path.remove(path.size() - 1);
        }

        if (node.right != null) {
            traversal(node.right, path, ans);
            path.remove(path.size() - 1);
        }
    }
}

LeetCode 404.左叶子之和

递归的核心步骤，确定递归传入参数，递归出口，单层处理逻辑，over.

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
class Solution {

    public int sumOfLeftLeaves(TreeNode root) {
        
        // null node is invalid
        if (root == null) return 0;
        // leaf node has no child node anymore
        if (root.left == null && root.right == null) return 0;

        // for every node, deal with its left, right and itself

        // left node
        int leftValue = 0;
        // if left child node is a leaf node
        if (root.left != null && root.left.left == null && root.left.right == null) {
             leftValue = root.left.val;
        }else {
            leftValue = sumOfLeftLeaves (root.left);
        }

        // right node
        int rightValue =  sumOfLeftLeaves(root.right);

        //itself
        return leftValue + rightValue;
    }

}

Posted on

LeetCode 104. 二叉树的最大深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maxDepth(TreeNode root) {
        return postorder(root);
    }

    private int postorder (TreeNode node) {

        if (node == null) {
            return 0;
        } else {
            // to some extent, this is post-order, LRD traversal
            return Math.max(postorder(node.left), postorder(node.right)) + 1;
        }

    }
}

没什么难度，后序遍历就行了

LeetCode 111.二叉树的最小深度

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
class Solution {
    public int minDepth(TreeNode root) {
        return postorder(root);
    }

    private int postorder (TreeNode node) {

        // recursion exits when node is empty
        if (node == null) {
            return 0;
        }

        if (node.left != null && node.right == null) {
            return postorder(node.left);
        }

        if (node.left == null && node.right != null) {
            return postorder(node.right);
        }

        // the else case means either this node is a leaf node or it has two children
        return Math.min(postorder(node.left), postorder(node.right)) + 1;


    }
}

注意单枝节点

LeetCode 222.完全二叉树的节点个数

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// class Solution {
//     public int countNodes(TreeNode root) {

//         if (root == null) {
//             return 0;
//         }

//         TreeNode node = root;
//         Queue<TreeNode> queue = new LinkedList();
//         queue.add(node);
//         int cnt = 0;

//         while(!queue.isEmpty()) {
//             int size = queue.size();

//             for (int i = 0; i < size; i++) {
//                 node = queue.poll();
//                 cnt++;

//                 if (node.left != null) {
//                     queue.add(node.left);
//                 }

//                 if (node.right != null) {
//                     queue.add(node.right);
//                 }
//             }
//         }

//         return cnt;
//     }
// }

class Solution {

    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }


        TreeNode left = root.left;
        int leftDepth = 0;
        while (left != null) {
            left = left.left;
            leftDepth++;
        }


        TreeNode right = root.right;
        int rightDepth = 0;
        while (right != null) {
            right = right.right;
            rightDepth++;
        }

        // if it is a full binary tree, easy culculation 
        if (leftDepth == rightDepth) {
            return (2 << leftDepth) - 1;
        }else {
            return countNodes(root.left) + countNodes(root.right) + 1;
        }

    }
    
}

第一种方法是遍历所有节点数数，O(n)， 第二种方法利用完全二叉树的特性，完全二叉树一定包含满二叉树，而满二叉树的节点数量易于计算。

Posted on

今天的重点是二叉树的层序遍历，思想也比较简单，分别用递归和队列实现了一下如下:

LeetCode 102.二叉树的层序遍历

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
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new LinkedList();

        if (root != null) {
            recursiveLevelOrder(0, ans, root);
        }

        return ans;
    }
    // an int variable 'level' is needed to record which level a node is
    private void recursiveLevelOrder (int level, List<List<Integer>> ans, TreeNode node) {
        
        if (node == null) {
            return;
        }

        // if the list which would record this node has not been created, new one and record
        if (ans.size() <= level) {
            List<Integer> list = new LinkedList<>();
            list.add(node.val);
            ans.add(list);
        }else{
            ans.get(level).add(node.val);
        }

        // actually, no need to check if left or right is null
        if (node.left != null) {
            recursiveLevelOrder(level + 1 , ans, node.left);
        }

        if (node.right != null) {
            recursiveLevelOrder(level + 1, ans, node.right);
        }

    }
}
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
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new LinkedList();

        if (root != null) {
            Queue<TreeNode> queue = new LinkedList<>();
            TreeNode node = root;

            queue.add(node);
            while (!queue.isEmpty()) {
                
                int size = queue.size();

                List<Integer> list = new LinkedList<>();
                for (int i = 0; i < size; i++) {
                    node = queue.poll();
                    list.add(node.val);
                    
                    if (node.left != null) {
                        queue.add(node.left);
                    }

                    if (node.right != null) {
                        queue.add(node.right);
                    }
                }
                ans.add(list);
            }
        }

        return ans;
    }
   
}

LeetCode 101.对称二叉树

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
class Solution {
    public boolean isSymmetric(TreeNode root) {

        if (root != null) {
            return compare(root.left, root.right);
        }

        return false;

    }

    private boolean compare (TreeNode left, TreeNode right) {

        if (left == null && right != null) {
            return false;
        }else if (left != null && right == null) {
            return false;
        }else if (left == null && right == null) {
            return true;
        }

        if ( left.val != right.val) {
            return false;
        }

        boolean outsidePair = compare(left.left, right.right);
        boolean insidePair = compare(left.right, right.left);

        return outsidePair && insidePair;

    }
}

LeetCode 226.翻转二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root != null) {
            reverseTree(root);
        }
        return root;
    }

    private void reverseTree(TreeNode node) {

        if (node == null) {
            return;
        }

        // swap the two nodes
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;

        reverseTree(node.left);
        reverseTree(node.right);

    }
}

Posted on Edited on

今天学习了如何使用递归法对二叉树进行前序、中序和后序遍历

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
// pre-order
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        
        List<Integer> ans = new LinkedList<>();
        if(root != null) {
            preorder(ans, root);
            return ans;
        }

        return ans;

    }

    private void preorder ( List<Integer> ans, TreeNode next) {

        // as this is pre-order scan
        // no matter whether this node has children or not
        // add its value in the ans first
        TreeNode node = next;
        ans.add(node.val);

        // if there is no child, just return
        if ( node.left == null && node.right == null) {
            return;
            // else let's call this method recursively on its children
        }else{
            if(node.left != null) {
                preorder(ans, node.left);
            }
    
            if(node.right != null) {
                preorder(ans, node.right);
            }
        }
    }
}

// in-order
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> ans = new LinkedList<>();

            if (root != null){
                inorder(ans, root);
            }

            return ans;
    }

    private void inorder (List<Integer> ans, TreeNode next) {
        TreeNode node = next;
        if (node.left == null){
            ans.add(node.val);

            if (node.right != null) {
                inorder(ans, node.right);
            }else{
                return;
            }
        }else{
            inorder(ans, node.left);
            ans.add(node.val);
            if (node.right != null) {
                inorder(ans, node.right);
            }
        }
    }
}

// post-order
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans = new LinkedList<>();

        if (root != null){
            postorder(ans, root);
        }

        return ans;
    }

    private void postorder(List<Integer> ans, TreeNode next) {
        TreeNode node = next;

        if (node.left == null && node.right == null) {
            ans.add(node.val);
            return;
        }else if (node.left != null && node.right != null){
            postorder(ans, node.left);
            postorder(ans, node.right);
            ans.add(node.val);
        }else {
            if ( node.left != null) {
                postorder(ans, node.left);
                ans.add(node.val);
            }

            if ( node.right != null) {
                postorder(ans, node.right);
                ans.add(node.val);
            }
        }
    }
}

/**
 * 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;
 *     }
 * }
 */

一开始写的不够简洁，修改了一下递归出口，修改后：

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/**
 * 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;
 *     }
 * }
 */
  
// pre-order
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new LinkedList<>();
        preorder(ans, root);
        return ans;

    }

    private void preorder ( List<Integer> ans, TreeNode cur) {
        // recursion exitrance condition
        if ( cur == null) {
            return;
        }
        // pre-order
        ans.add(cur.val);
        preorder(ans, cur.left);
        preorder(ans, cur.right);
    }
}

// in-order
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new LinkedList<>();
        inorder(ans, root);
        return ans;
    }

    private void inorder (List<Integer> ans, TreeNode cur) {
        // recursion exitrance condition
        if ( cur == null) {
            return;
        }

        // inorder 
        inorder(ans, cur.left);
        ans.add(cur.val);
        inorder(ans, cur.right);
    }
}

// post-order
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans = new LinkedList<>();
        postorder(ans, root);
        return ans;
    }

    private void postorder(List<Integer> ans, TreeNode cur) {

        // recursion exitrance condition
        if (cur == null) {
            return;
        }

        // post-order
        postorder(ans, cur.left);
        postorder(ans, cur.right);
        ans.add(cur.val);
    }
}

除了使用递归方法，我们还可以使用一个栈结构来模拟递归行为：

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
// pre-order
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new LinkedList<>();

        if (root == null) {
            return ans;
        }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode node;
        stack.push(root);
      
        while (!stack.isEmpty()) {
            node = stack.pop();
            ans.add(node.val);

            if (node.right != null) {
                stack.push(node.right);
            }

            if (node.left != null) {
                stack.push(node.left);
            }

            
        }

        return ans;

    }
}

// in-order
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new LinkedList<>();

        if (root == null) {
            return ans;
        }

        Stack<TreeNode> visited = new Stack<>();
        TreeNode node = root;
        while (node != null || !visited.isEmpty()) {

            // go along the left side until touching the leftmost leaf node
            if (node != null) {
                visited.push(node);
                node = node.left;
            }else {

                // pop the last element we visited, records its value and 
                // point to its right node
                node = visited.pop();
                ans.add(node.val);
                node = node.right;
            }

        }
        return ans;
    }

}

// post-order
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans = new LinkedList<>();

        if (root == null) {
            return ans;
        }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;

        // post order left right root, reverse to root, right, left in stack
        // see what? root, right, left, similar to pre-order but get child nodes swapped
        // thus, it is easy to think how about let's slightly change the code for pre-order
        stack.push(node);
        while (!stack.isEmpty()) {
            ans.add(node.val);

            if (node.left != null) {
                stack.push(node.left);
            }

            if (node.right != null) {
                stack.push(node.right);
            }

            node = stack.pop();
        }

        // now we get the values but in root right left, we need to reverse the ans list
        for (int i = 0, j = ans.size() - 1, temp = 0; i < j; i++, j--) {
            temp = ans.get(i);
            ans.set(i, ans.get(j));
            ans.set(j, temp);
        }

        return ans;
    }
}

Posted on

LeetCode 239.滑动窗口最大值

这道题其实还挺有意思的， 一个直观的想法是在遍历时对于窗口元素二次遍历寻找最大值，时间复杂度为O(nk)， 超时。这个办法的问题其实是，在每次移动窗口时，我们只是移除了一个元素，并新增加一个元素，但是却需要二次遍历当前的窗口，即上一个求出的最大值无法给下次寻找最大值带来任何便利。

一个优化思路是cache住上个窗口的最大值相关的部分信息，带入下一个窗口，这里使用一个定制的单调递减队列实现，具体的实现如下：

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {

        MyQueue queue = new MyQueue();

        List<Integer> ans = new LinkedList<>();


        for (int i = 0; i < k; i++) {
            queue.add(nums[i]);
        }
        ans.add(queue.peek());


        for (int i = k; i < nums.length; i++) {
            
            queue.add(nums[i]);
            queue.poll(nums[i - k]);
            ans.add(queue.peek());

        }

        return ans.stream().mapToInt(i -> i).toArray();
    }

    // customize a monotonically decreasing queue
    class MyQueue {
        Deque<Integer> deque = new LinkedList<>();

        // if the slide window rule out our head element
        // then pop it, else pop nothing, as we do not cache
        // them actaully
        public void poll (int val) {
            if ( val == deque.peek()) {
                deque.poll();
            }
        }

        // for every new added element, try to add them into the queue
        // if they are less then any elements, just add it at the last
        // else delete those less than it, as they are meanningless now

        public void add (int val) {
            // note here, we need to remain the same large element within the queue
            // if here we use val >= deque.last, we would rule out the same large element
            while (!deque.isEmpty() && val > deque.peekLast()) {
                deque.removeLast();
            }
            deque.addLast(val);
        }

        // since we maintain such a queue that the head element is always our
        // maximum value in this window
        public int peek() {
            return deque.peek();
        }

    }
}

LeetCode 347.前k个高频元素

这道题目的难度不高，首先对数组内出现的数计算频次，使用hashmap，然后对entry按照value排序，然后输出，

看了下题解，很多都是用优先队列，小顶堆来做，暂时不是很熟悉。

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
class Solution {
    public int[] topKFrequent(int[] nums, int k) {

        // step 1 : count the frequence of each element
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])){
                map.put(nums[i], map.get(nums[i]) + 1);
            }else {
                map.put(nums[i], 1);
            }
        }

        // step 2 : sort the frequences
        List<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());
      	// can use lambda expression to simplify the declaration of the comparator
      	// list.sort((o1,o2)-> (- o1.getValue().compareTo(o2.getValue())));
        list.sort(new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2){
                // the defult order is natrual order i.e. increasing order
                return -o1.getValue().compareTo(o2.getValue());
            }
        });

        // steo 3 : output the ans
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            ans[i] = list.get(i).getKey();
        }

        return ans;
    }
}

另外一种思路是使用小顶堆，即优先队列进行排序和输出操作，注意小顶堆中，最小的元素处于head节点，然后从后向前依次弹出。

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 int[] topKFrequent2(int[] nums, int k) {

    // step 1 : count the frequence of each element
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
    }

    // step 2 : sort the frequences
    PriorityQueue<int[]> pq = new PriorityQueue<>((pair1,pair2)->pair1[1]-pair2[1]);
    for (Map.entry<Integer, Integer> entry : map.entrySet()) {
        if (pq.size() < k) {
            pq.add(new int[]{entry.getKey(), entry.getValue()});
        }else {
            if (entry.getValue() > pq.peek()[1]){
                pq.poll();
                pq.add(entry);
            }
        }
    }

    // steo 3 : output the ans
    int[] ans = new int[k];
    for (int i = k - 1; i >= 0; i--) {
        ans[i] = pq.poll()[0];
    }

    return ans;
}

Posted on

今天的主要内容是栈的应用:

LeetCode 20.有效的括号

这道题算是栈的经典应用了，栈这种数据结构的核心在一它能够提供前序元素的信息

给定一串字符串包含’(‘, ‘)’, ‘[‘, ‘]’, ‘{‘, ‘}’, 判断其括号是否匹配，整体是否有效

一个易见的思路是使用栈，将所有左侧符号都存起来，在遇到右侧符号时将目前栈顶的元素弹出，如果能匹配上则继续，如果匹配不上则返回false；如果遍历完整个字符串栈为空，则说明为有效的括号。

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
class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            char c1 = s.charAt(i);
            // if this char is left side, push it into stack
            if (c1 == '(' || c1 == '[' || c1 == '{') {
                stack.push(c1);
            }else {

                // if stack is empty and a right side char comes
                // return false
                if (stack.isEmpty()) {
                    return false;
                }

                // else let's check if there is a pair
                char c2 = stack.pop();
                if ( c1 == ')' && c2 == '(' ||
                     c1 == ']' && c2 == '[' ||
                     c1 == '}' && c2 == '{') {
                        continue;
                     }else {
                        return false;
                     }
            }
        }
        
        // if after checking, there is no chars left in the stack
        // it means that they are all pairs
        return stack.isEmpty();

    }
}

LeetCode 1047.删除字符串中的所有相邻重复项

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
class Solution {
    public String removeDuplicates(String s) {

        char[] chars = s.toCharArray();
        Stack<Character> stack = new Stack<>();
        
      	// full scan the whole string
        for (char c : chars) {
          	// if stack is not empty, pop the top element
          	// compare if it is the same with the pointed one
          	// if not push them back
            if (!stack.empty()) {
                char c2 = stack.pop();
                if (c2 != c){
                    stack.push(c2);
                    stack.push(c);
                }
            }else {
                stack.push(c);
            }
        }
				
      	// pop the left elements
        if (!stack.isEmpty()){
            int size = stack.size();
            char[] ans = new char[size];
            while (size > 0) {
                ans[--size] = stack.pop();
            }

            return String.valueOf(ans);
        }else {
            return "";
        }
    }
}

LeetCode 150.逆波兰表达式

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 {
    public int evalRPN(String[] tokens) {

        Stack<String> stack = new Stack<>();
        String s1, s2;
        int temp = 0;;

        for (String s : tokens) {

            switch (s) {
                case "+" :
                    s1 = stack.pop();
                    s2 = stack.pop();
                    temp = Integer.valueOf(s2) + Integer.valueOf(s1);
                    stack.push(String.valueOf(temp));
                    break;
                case "-" :
                    s1 = stack.pop();
                    s2 = stack.pop();
                    temp = Integer.valueOf(s2) - Integer.valueOf(s1);
                    stack.push(String.valueOf(temp));
                    break;
                case "*" :
                    s1 = stack.pop();
                    s2 = stack.pop();
                    temp = Integer.valueOf(s2) * Integer.valueOf(s1);
                    stack.push(String.valueOf(temp));
                    break;
                case "/" :
                    s1 = stack.pop();
                    s2 = stack.pop();
                    temp = Integer.valueOf(s2) / Integer.valueOf(s1);
                    stack.push(String.valueOf(temp));
                    break;
                default:
                stack.push(s);
            }

        }

        return Integer.valueOf(stack.pop());
    }
}

了解了后缀表达式的规则后就会发现，这是一种很适合使用栈来进行计算的表达式，从左到右遍历字符串，遇到数字就压入栈，遇到操作符就弹出两个数字计算，然后将结果压入栈，最后留在栈中的数字即为计算结果。