[每天两道题]坚持找到工作为止

98. Validate Binary Search Tree
这个题描述的有点模糊，它实际上要求，根节点的左子树，所有节点都要比根节点小，右子数所有节点都比根节点大。
这个题两个做法，第一个是利用bst特性，bst中序遍历，出来的就是一个排好序的数列，所以才叫in-order traversal. 我们中序遍历一次，然后看出来的结果是不是有序。
第二个做法就是把当前树的上限max和下限min都从上一层传进来。然后若是根节点等于或超出范围，就返回false。然后往下一层传，下一层的左子树范围就是 （min,curr），右子树范围就是(curr,max)。
这里注意初始化范围必须为［long.min  long.max]，因为node.val可以为int.max, int.min，所以有个特殊情况 ： 若是刚开始节点就是个int.min或者int.max，我们若是把初始范围定义在[int.min, int.max]就会导致刚开始root就等于范围边缘了，就会返回一个错误的false。所以我们刚开始要定义得比int.min,intmax更大一点。为了方便就定义long.min, long.max。你也可以定义成long max = int.max + 1这样的，反正只要初始化范围比node.val的取值范围更大就行。
所以代码就是

1. class Solution {
   
2.     public boolean isValidBST(TreeNode root) {
   
3.         return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
   
4.     }
   
5.    
   
6.     private boolean helper(TreeNode node, long min, long max) {
   
7.         if(node == null) return true;
   
8.         
   
9.         long curr = node.val;
   
10.         if(curr <= min || curr >= max) {
    
11.             return false;
    
12.         }
    
13.         return helper(node.left, min, curr) && helper(node.right, curr, max);
    
14.     }
    
15. }
    

复制代码

99. Recover Binary Search Tree

本题用到了morri遍历。这种遍历方法可以在o(n)的时间，o(1)的空间复杂度内，不用递归就完成对bst的遍历。

模板各位自己可以搜索。那么如何利用它解决本题呢？因为morri遍历，过程本身就是去找我们当前节点，它在输出的时候上一个节点是什么。你可以想象成，中序遍历一个bst，结果应该是一个排序好的数组nums，若是我当前节点，最后在数组种的位置是i，也就是currNode.val = nums[i]，那么morri遍历其实就是去找nums[i - 1]对应的节点是什么。

怎么找这里就不详细总结了，总之方法就是先看有没有左子树，有的话，在左子树里面找最右的节点，它就是我们的前置节点。然后问题是找到了怎么再转回来，方法就是把这个前置节点的right和我们现在的节点连上，其实就是把nums[i-1] nums[i]连上。然后当前节点node= node.left。也就是往左子树继续遍历。同样，若是转了一圈，我们又转回当前节点了，我们又找到了一次左子树的最右节点，此时我们发现它的right是我们自己，已经连接上了， 那么此时我们就输出前置节点，再把前直节点断开。
这是处理左子树的情况，若是没有左子树，那么我们直接输出当前节点，再进入右子树。

然后怎么解决问题，我们用一个pre节点，记录一下当前节点上一个遍历的节点是什么。这个节点其实就是前置节点，按照bst的中序遍历输出应该是从小到大。所以我们每次输出节点的时候，和前置节点比较一下值，若是发现前置节点反而比较大，说明这个前置节点一定是反的，但是当前节点不一定是错的，我们还要继续用后面的节点，去比较这个错误的前置节点。所以我们用一个x记录一下这个错误的前置节点，并且我们只记录一次，因为比如 错误的bst最后输出的顺序是 [1, 4,3,2, 5] 也就是2和4交换了。那么我们在3，4的时候就会发现4是错误的，但是3的顺序是对的，所以我们还要继续比较3后面的数字。

我们记录一下前置节点，和当前节点。之后我们每次输出，比较一下记录的前置节点和当前节点，若是当前节点还是比记录的前置节点小，那么我们继续更新当前节点为第二个错误的节点，比如上个例子种，我们比较完3 、4，记录下第一个错误数字是4之后，我们要继续比较4和2，发现2比4还是小，说明2有可能是第二个错误数字，然后我们继续比较4、5，此时发现顺序又对了，那么我们就确定了2，4的是错误的节点。

这个解法非常高大上，也非常抽象难想。我也是一边总结一边才彻底想明白其中的门路的，此种题应该只能背诵。没有什么其他好的办法。
代码是

1. class Solution {
   
2.     public void recoverTree(TreeNode root) {
   
3.         TreeNode pre = null;
   
4.         TreeNode x = null;
   
5.         TreeNode y = null;
   
6.          while(root != null) {
   
7.             
   
8.              if(root.left == null) {
   
9.                  if(pre != null && pre.val > root.val) {
   
10.                      if(x == null) x = pre;
    
11.                      y = root;
    
12.                  }
    
13.                  pre = root;
    
14.                  
    
15.                  root = root.right;
    
16.              }else{
    
17.                  TreeNode rightMost = root.left;
    
18.                  while(rightMost.right != null && rightMost.right != root) {
    
19.                      rightMost = rightMost.right;
    
20.                  }
    
21.                            
    
22.                  if(rightMost.right == root) {
    
23.                      if(pre != null && pre.val > root.val) {
    
24.                          if(x == null)x  = pre;
    
25.                          y = root;
    
26.                      }
    
27.                      pre = root;
    
28.                      
    
29.                      rightMost.right = null;
    
30.                      root = root.right;
    
31.                  }else {
    
32.                      rightMost.right = root;
    
33.                      root = root.left;
    
34.                  }
    
35.              }
    
36.          }
    
37.         
    
38.         int temp = x.val;
    
39.         x.val = y.val;
    
40.         y.val =temp;
    
41.     }
    
42. }

复制代码

100. Same Tree
这个题还是挺重要的，如何比较两个树是相同的。
方法就是比较二者的值是否相同，然后分别递归比较左右子树。
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) return true;
        if(p == null || q == null) return false;
        return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}
101. Symmetric Tree
这个题和上一道是一样的解法，只是改动一下递归的时候，左右的顺序。
public boolean isSymmetric(TreeNode root) {
        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;
        if(left.val != right.val) return false;
        
        return helper(left.left, right.right) && helper(left.right, right.left);
    }

102. Binary Tree Level Order Traversal
这道题其实应该是简单难度，用bfs的层序遍历就可以了。定义一个queue，每次取出本层数量的节点，然后把他们的左右孩子再添加进去即可。

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        
        List<List<Integer>> rs = new ArrayList<>();
        if(root == null) return rs;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> temp = new ArrayList<>();
            for(int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                temp.add(node.val);
                if(node.left != null) {
                    queue.offer(node.left);
                }
                if(node.right != null) {
                    queue.offer(node.right);
                }
            }
            rs.add(temp);
        }
        return rs;
    }
}

105. Construct Binary Tree from Preorder and Inorder Traversal
本题是好题，非常考验我们对于树的遍历的理解。一定要很明白这两种遍历的性质。并且递归的参数很多，要想得非常明白。
preorder的结果，输出性质是，第一个节点一定是根，然后后面是根左子树 + 右子树。左子树一定在右子树的前面。

所以我们每次递归可以用Preoder的结果来生成新的root。
然后就是看这个root的左右子树是什么。preorder是看不出左右子树的大小的。但是inorder可以。若是我们知道某一个节点inorder[i]是根，那么它的左右两边一定是左右子树的大小。注意这个左右两边不是指一直到0和len -1，而是到本节点的范围为止。

比如preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
我们先知道preorder[0] = 3一定是根节点。然后我们看inorder里面，3的左边有一个数字9，右边有3个数字15 20 7。所以3的左子树大小是1， 右子树大小是3。
那么在preorder里面，我们就知道3后面，1个数字9是左子树，再紧接3个数字[20，15 ,7]是右子树。
然后我们递归算左子树，此时左子树左右两边的范围，在preorder里就是[1,1]，在inorder里就是[0,0]。
然后递归算右子树，此时右字数左右两边的范围，在preorder里就是[2,4]，在inorder里就是[2,4]。
如此递归下去，直到左右两边的范围缩小到没有，就是null节点了。所以代码就是

1. class Solution {
   
2.     public TreeNode buildTree(int[] preorder, int[] inorder) {
   
3.         Map<Integer, Integer> map = new HashMap<>();
   
4.         for(int i = 0; i < inorder.length; i++) {
   
5.             map.put(inorder[i], i);
   
6.         }
   
7.         
   
8.         return helper(map, preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
   
9.     }
   
10.    
    
11.     private TreeNode helper(Map<Integer, Integer> map , int[] preorder, int[] inorder, int preStart, int preEnd, int inorS, int inorE) {
    
12.         if(inorS > inorE || preStart > preEnd) return null;
    
13.         TreeNode root = new TreeNode(preorder[preStart]);
    
14.         
    
15.         int inorderIdx = map.get(preorder[preStart]);
    
16.         
    
17.         int leftTreeSize = inorderIdx - inorS;
    
18.         int rightTreeSize = inorE - inorderIdx;
    
19.         
    
20.         root.left = helper(map, preorder, inorder, preStart + 1, preStart + leftTreeSize, inorS, inorderIdx - 1);
    
21.         root.right = helper(map, preorder, inorder, preStart + leftTreeSize + 1,preStart + leftTreeSize + rightTreeSize, inorderIdx + 1, inorE );
    
22.         
    
23.         return root;
    
24.     }
    
25. }

复制代码

104. Maximum Depth of Binary Tree
本题也十分简单，用dfs，每次返回下一层递归传上来的深度再+1返回给上一层递归，返回条件是root == null return 0。然后每次我们返回左右子树的递归结果中更大的一个。

这道题可以用一行代码就解决：

1. class Solution {
   
2.     public int maxDepth(TreeNode root) {
   
3.         return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
   
4.     }
   
5. }

复制代码

103. Binary Tree Zigzag Level Order Traversal
层序遍历，用一个boolean表示是不是偶数行，若是偶数行，就反转一下本行的list即可。非常简单。

1. class Solution {
   
2.     public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
   
3.         List<List<Integer>> rs = new ArrayList<>();
   
4.         if(root == null) return rs;
   
5.         Queue<TreeNode> queue = new LinkedList<>();
   
6.         queue.add(root);
   
7.         boolean dir = false;
   
8.         
   
9.         while(!queue.isEmpty()) {
   
10.             int size = queue.size();
    
11.             List<Integer> list = new ArrayList<>();
    
12.             for(int i = 0; i < size; i++) {
    
13.                 TreeNode node = queue.poll();
    
14.                 list.add(node.val);
    
15.                 if(node.left != null) queue.offer(node.left);
    
16.                 if(node.right != null) queue.offer(node.right);
    
17.             }
    
18.             
    
19.             if(dir) {
    
20.                 Collections.reverse(list);
    
21.             }
    
22.             dir = !dir;
    
23.             rs.add(list);
    
24.         }
    
25.         return rs;
    
26.     }
    
27. }
    

复制代码

108. Convert Sorted Array to Binary Search Tree
这道题其实是前面两道关于生成树的前置问题，面试时若是想降低难度，是可以先出这道题的。
还是用递归，每次取出中间位置作为根，左面就是左子树，右面就是右子树。然后递归下一层，左子树的范围就是[0, mid -1], 右面就是[mid + 1, len - 1]。再继续递归。

1. class Solution {
   
2.    
   
3.     public TreeNode sortedArrayToBST(int[] nums) {
   
4.        return helper(nums, 0, nums.length - 1);
   
5.     }
   
6.    
   
7.     private TreeNode helper(int[] nums, int l , int r) {
   
8.         if(l > r) return null;
   
9.         int mid = l + ((r - l) >> 1);
   
10.         TreeNode root = new TreeNode(nums[mid]);
    
11.         
    
12.         root.left = helper(nums, l, mid - 1);
    
13.         root.right = helper(nums, mid + 1, r);
    
14.         
    
15.         return root;
    
16.     }
    
17. }

复制代码

107. Binary Tree Level Order Traversal II
这道题有BFS和DFS两个解法，BSF的写法非常简单，每次添加答案的时候，往前面添加就可以了。也就是其实答案逆序即可。

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

复制代码

106. Construct Binary Tree from Inorder and Postorder Traversal
这道题和上一个preorder是一样的。因为postorder就是preorder的逆序，所以把它翻转一下就和上一道题一样了。这道题我认为若是没有前两道题的话，直接做这道题的话，是有一定难度的。

1. class Solution {
   
2.     public TreeNode buildTree(int[] inorder, int[] postorder) {
   
3.         //inorder =   [9,3,15,20,7]
   
4.         //               ^
   
5.         //postorder = [9,15,7,20,3]
   
6.         //                       ^
   
7.         
   
8.         Map<Integer, Integer> map = new HashMap<>();
   
9.         for(int i = 0; i < inorder.length; i++) {
   
10.             map.put(inorder[i], i);
    
11.         }
    
12.         
    
13.         return helper(map, inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1);
    
14.     }
    
15.    
    
16.     private TreeNode helper(Map<Integer, Integer> map, int[] inorder, int[] postorder, int inorderL, int inorderR, int postL, int postR) {
    
17.         if(inorderL > inorderR || postL > postR) return null;
    
18.             
    
19.         TreeNode node = new TreeNode(postorder[postR]);
    
20.         int i = map.get(postorder[postR]);
    
21.         
    
22.         int leftTreeSize = i - inorderL;
    
23.         int rightTreeSize = inorderR - i;
    
24.         
    
25.         node.left = helper(map, inorder, postorder, inorderL, i - 1, postR - rightTreeSize - leftTreeSize, postR - rightTreeSize - 1);
    
26.         node.right = helper(map, inorder, postorder, i + 1, inorderR, postR - rightTreeSize, postR - 1);
    
27.         
    
28.         return node;
    
29.         
    
30.     }
    
31. }

复制代码