LeetCode(96) -- 113, 114, 116, 117, 120

P113. Path Sum II (Medium)

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

My Solution

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        dfs(root, sum, 0, new ArrayList<>());
        return ans;
    }

    private void dfs(TreeNode node, int sum, int currentSum, List<Integer> tempList) {
        if (node == null) {
            return;
        }
        if (node.left == null && node.right == null && sum == currentSum + node.val) {
            tempList.add(node.val);
            ans.add(new ArrayList<>(tempList));
            tempList.remove(tempList.size() - 1);
            return;
        }
        if (node.left != null) {
            tempList.add(node.val);
            dfs(node.left, sum, currentSum + node.val, tempList);
            tempList.remove(tempList.size() - 1);
        }
        if (node.right != null) {
            tempList.add(node.val);
            dfs(node.right, sum, currentSum + node.val, tempList);
            tempList.remove(tempList.size() - 1);
        }
    }
}

99%

Solution

class Solution {
    
    private void recurseTree(TreeNode node, int remainingSum, List<Integer> pathNodes, List<List<Integer>> pathsList) {
        
        if (node == null) {
            return;
        }
        
        // Add the current node to the path's list
        pathNodes.add(node.val);
        
        // Check if the current node is a leaf and also, if it
        // equals our remaining sum. If it does, we add the path to
        // our list of paths
        if (remainingSum == node.val && node.left == null && node.right == null) {
            pathsList.add(new ArrayList<>(pathNodes));
        } else {
            
            // Else, we will recurse on the left and the right children
            this.recurseTree(node.left, remainingSum - node.val, pathNodes, pathsList);
            this.recurseTree(node.right, remainingSum - node.val, pathNodes, pathsList);
        }
        
        // We need to pop the node once we are done processing ALL of it's
        // subtrees.
        pathNodes.remove(pathNodes.size() - 1);
    }
    
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> pathsList = new ArrayList<List<Integer>>();
        List<Integer> pathNodes = new ArrayList<Integer>();
        this.recurseTree(root, sum, pathNodes, pathsList);
        return pathsList;        
    }
}

这个代码跟我的差不多，但比我的简洁一点点。

P114. Flatten Binary Tree to Linked List (Medium)

Given a binary tree, flatten it to a linked list in-place.

My Solution

class Solution {
    public void flatten(TreeNode root) {
        flattenAndGetLeaf(root);
    }

    private TreeNode flattenAndGetLeaf(TreeNode root) {
        if (root == null) {
            return null;
        }
        if (root.left == null && root.right == null) {
            return root;
        }
        TreeNode leftLeaf = flattenAndGetLeaf(root.left);
        TreeNode rightLeaf = flattenAndGetLeaf(root.right);
        if (leftLeaf == null) {
            return rightLeaf;
        }
        TreeNode right = root.right;
        root.right = root.left;
        root.left = null;
        if (rightLeaf == null) {
            return leftLeaf;
        }
        leftLeaf.right = right;
        return rightLeaf;
    }
}

100%

Solution

方法一：

class Solution {
    
    private TreeNode flattenTree(TreeNode node) {
        
        // Handle the null scenario
        if (node == null) {
            return null;
        }
            
        // For a leaf node, we simply return the
        // node as is.
        if (node.left == null && node.right == null) {
            return node;
        }
        
        //Recursively flatten the left subtree
        TreeNode leftTail = this.flattenTree(node.left);
        
        // Recursively flatten the right subtree
        TreeNode rightTail = this.flattenTree(node.right);
        
        // If there was a left subtree, we shuffle the connections
        // around so that there is nothing on the left side
        // anymore.
        if (leftTail != null) {
            leftTail.right = node.right;
            node.right = node.left;
            node.left = null;
        }
        
        // We need to return the "rightmost" node after we are
        // done wiring the new connections. 
        return rightTail == null ? leftTail : rightTail;
    }
    
    public void flatten(TreeNode root) {
        
        this.flattenTree(root);
    }
}

方法二感觉不太好，不copy了。 方法三：

class solution {
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode node = root;
        while (node != null) {
            if (node.left != null) {
                TreeNode rightmost = node.left;
                while (rightmost.right != null) {
                    rightmost = rightmost.right;
                }
                rightmost.right = node.right;
                node.right = node.left;
                node.left = null;
            }
            node = node.right;
        }
    }
}

这个方法很好。因为flatten之后，左子树的最后一个，一定是最右边最底下的那个节点，所以直接把右子树挂在那个上面，然后用左子树替换右子树。然后再往下走一格。

P116. Populating Next Right Pointers in Each Node (Medium)

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

My Solution

按层级遍历这棵树，BFS，然后依次连接就可以了。

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return null;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            Node prev = queue.remove();
            if (prev.left != null) {
                queue.add(prev.left);
                queue.add(prev.right);
            }
            for (int i = 1; i < size; i++) {
                Node node = queue.remove();
                prev.next = node;
                prev = prev.next;
                if (node.left != null) {
                    queue.add(node.left);
                    queue.add(node.right);
                }
            }
        }
        return root;
    }
}

50%

Solution

方法一：

class Solution {
    public Node connect(Node root) {
        
        if (root == null) {
            return root;
        }
        
        // Initialize a queue data structure which contains
        // just the root of the tree
        Queue<Node> Q = new LinkedList<Node>(); 
        Q.add(root);
        
        // Outer while loop which iterates over 
        // each level
        while (Q.size() > 0) {
            
            // Note the size of the queue
            int size = Q.size();
            
            // Iterate over all the nodes on the current level
            for(int i = 0; i < size; i++) {
                
                // Pop a node from the front of the queue
                Node node = Q.poll();
                
                // This check is important. We don't want to
                // establish any wrong connections. The queue will
                // contain nodes from 2 levels at most at any
                // point in time. This check ensures we only 
                // don't establish next pointers beyond the end
                // of a level
                if (i < size - 1) {
                    node.next = Q.peek();
                }
                
                // Add the children, if any, to the back of
                // the queue
                if (node.left != null) {
                    Q.add(node.left);
                }
                if (node.right != null) {
                    Q.add(node.right);
                }
            }
        }
        
        // Since the tree has now been modified, return the root node
        return root;
    }
}

思路跟我差不多，但是我没想到可以用peek()先看一眼下一个节点，而是把第一个节点在循环之前就取出来了，代码就比较难看。学习这个代码就行了。

方法二：

class Solution {
    public Node connect(Node root) {
        
        if (root == null) {
            return root;
        }
        
        // Start with the root node. There are no next pointers
        // that need to be set up on the first level
        Node leftmost = root;
        
        // Once we reach the final level, we are done
        while (leftmost.left != null) {
            
            // Iterate the "linked list" starting from the head
            // node and using the next pointers, establish the 
            // corresponding links for the next level
            Node head = leftmost;
            
            while (head != null) {
                
                // CONNECTION 1
                head.left.next = head.right;
                
                // CONNECTION 2
                if (head.next != null) {
                    head.right.next = head.next.left;
                }
                
                // Progress along the list (nodes on the current level)
                head = head.next;
            }
            
            // Move onto the next level
            leftmost = leftmost.left;
        }
        
        return root;
    }
}

这个方法比较好，用上一层已经建立的连接，构建下一层的连接。

P117. Populating Next Right Pointers in Each Node II (Medium)

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

My Solution

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return null;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Node poll = queue.poll();
                if (i < size - 1) {
                    poll.next = queue.peek();
                }
                if (poll.left != null) {
                    queue.add(poll.left);
                }
                if (poll.right != null) {
                    queue.add(poll.right);
                }
            }
        }
        return root;
    }
}

跟上一题基本一样，只不过这次不是完美树了。上一次我的BFS解法本来也没指望它是完美树，所以完全可以照搬过来。

P120. Triangle (Medium)

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

题目描述不清楚，试了两次才明白这是一个DFS的题。

My Solution

public class P120_Triangle {
    int min = Integer.MAX_VALUE;
    int sum = 0;
    public int minimumTotal(List<List<Integer>> triangle) {
        dfs(triangle, 0, 0);
        return min;
    }

    private void dfs(List<List<Integer>> triangle, int depth, int index) {
        if (depth == triangle.size()) {
            return;
        }
        Integer val = triangle.get(depth).get(index);
        sum += val;
        if (depth == triangle.size() - 1) {
            min = Math.min(min, sum);
        } else {
            dfs(triangle, depth + 1, index);
            dfs(triangle, depth + 1, index + 1);
        }
        sum -= val;
    }
}

Time Limit Exceeded

看了讨论区，发现如果简单地用DFS做，会有很多重复计算。需要用DP优化。

The best Solution

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.size() == 0) {
            return 0;
        }
        int size = triangle.size();
        int[] dp = new int[size];
        
        for (int i = size - 1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                if (i == size - 1) {
                    dp[j] = triangle.get(i).get(j);
                } else {
                    dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
                }
            }
        }
        return dp[0];
    }
}

从下到上构建，两两依次取较小的，加上上一层，就是需要的结果。