Leetcode-Tree

Binary Tree 的遍历，Time: O(n), Space: O(n).
先序遍历：
preorder(node)
visit(node) //最先遍历node
preorder(node.left)
preorder(node.right)
中序遍历：
inorder(node)
inorder(node.left)
visit(node) //node在中间
inorder(node.right)
后序遍历：
postorder(node)
postorder(node.left)
postorder(node.right)
visit(node) //最后遍历node
pre, in, post, 都是依据visit(node)根结点在第一个、中间、第三个被访问的情况来命名的。确定node在第几个被访问之后，剩下的两个位置，先访问left再访问right，从而确定了三个位置的遍历顺序。

Recursive：【递归（英语：Recursion），又译为递回】

Preorder

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        recursive(list,root);
        return list;
    }
    
    private void recursive(List list,TreeNode root){
        if(root==null) return;
        list.add(root.val);
        recursive(list,root.left);
        recursive(list,root.right);
    }
}

Inorder

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        recursive(list,root);
        return list;
    }
    
    private void recursive(List list, TreeNode root){
        if(root==null) return;
        recursive(list,root.left);
        list.add(root.val);
        recursive(list,root.right);
        
    }
}

Postorder

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        recursive(list,root);
        return list;
    }
    
    private void recursive(List list,TreeNode root){
        if(root==null) return;
        recursive(list,root.left);
        recursive(list,root.right);
        list.add(root.val);
    }
}

Iterative: 【Iteration is the repetition of a process in order to generate a (possibly unbounded) sequence of outcomes.迭代是重复反馈过程的活动。每一次对过程的重复被称为一次“迭代”。】

Preorder
特点：1)和postorder很像。

    public List<Integer> preorderTraversal(TreeNode root) {    
        List<Integer> list = new ArrayList<>();
        if(root==null) return list;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode current = stack.pop();
            list.add(current.val);
            if(current.right != null) stack.push(current.right);
            if(current.left != null) stack.push(current.left);
        }
        return list;
    }

Inorder
法1，带current写法
特点：1) 第一个while循环的条件。2) 内层用了while循环来寻找最左端的left。
inorder的语句TreeNode current = root，不同于另外两个的stack.push(root) 。

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root==null) return list;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        while(!(stack.isEmpty()&&current==null)){
            while (current!=null){
                stack.push(current);
                current=current.left;
            }
            current=stack.pop();
            list.add(current.val);
            current=current.right;           
        }
        return list;        
    }

法2，inorder 的iterative写法, 不用current：

public List<Integer> inorderTraversal2(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    Stack<TreeNode> stack = new Stack<>();
    pushAllLeft(root, stack);
    while (!stack.isEmpty()) {
        TreeNode cur = stack.pop();
        res.add(cur.val);
        pushAllLeft(cur.right, stack);
    }
    return res;
}

public void pushAllLeft(TreeNode node, Stack stack){
    while (node != null) {
        stack.add(node);
        node = node.left;
    }
}

Postorder:
特点：
1)和preorder很像。2)用了list.add(位置,插入数字)方法。也可用LinkedList, 和LinkedList独有的addFirst() 方法。

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()) {
            TreeNode current = stack.pop();
            list.add(0,current.val);     //在位置0插入current值
            if(current.left!=null) {
              stack.push(current.left);
            }
            if(current.right!=null) {
               stack.push(current.right); 
            }
        }
        return list;      
    }

Leetcode 102. Binary Tree Level Order Traversal. 【Medium】
两种方法都是： Time: O(n), Space: O(n).
方法1，运用queue，一层层遍历并记录。

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) return res;   //必须检查，不然会进入while，在list.add(current.val)处出错
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();  //必须单独写出size，因为在for循环过程中size会改变
            List<Integer> list = new ArrayList<>();
            for(int i=0; i<size; i++){   
                TreeNode current = queue.poll();
                list.add(current.val);
                if(current.left != null) queue.offer(current.left);
                if(current.right != null) queue.offer(current.right);
            }
            res.add(list);
        }
        return res;
    }
}

方法2，用先序遍历实现层次遍历。

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) return res; //本题可以注释这行。但二叉树很多题型都需要检查这个。所以保留这个养成习惯
        helper(res,root,0);
        return res;
    }
    
    private void helper(List<List<Integer>> res, TreeNode root, Integer level){
        if(root == null) return;
        if(level == res.size()){    // >= 也可。因为遍历前并不知道level有几层，所以每次都需要检查level是否超出目前的res所存的层数
            res.add(new ArrayList<>());
        }
        res.get(level).add(root.val);
        helper(res,root.left,level+1);
        helper(res,root.right,level+1);
        
    }

Leetcode 100. Same Tree. 【Easy】
前两个if判断，都是为recursive服务。

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if((p==null && q!=null)||(p!=null && q==null)) return false;
        if(p==null && q==null) return true;
        if(p.val != q.val) return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

Leetcode 101. Symmetric Tree. 【Easy】
和100很类似，关键在于最后一句的判断，顺序对称就行。
Symmetric, 对称的。Symmetric is something where one side is a mirror image or reflection of the other.

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null) return true;
        return helper(root.left,root.right);
    }
    
    private boolean helper(TreeNode p, TreeNode q){
        if(p==null && q==null) return true;
        if((p==null&&q!=null)||(p!=null&&q==null)) return false;
        if(p.val != q.val) return false;
        return helper(p.left,q.right) && helper(p.right,q.left);
    }
}

Leetcode 226. Invert Binary Tree 【Easy】
invert = reverse, 翻转
tree的题目大多都可以用BFS和DFS做。
BFS：Breadth-First-Search，广度优先搜索算法
DFS：Depth-First-Search，深度优先搜索算法
1）DFS,深度优先

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) return root;
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}

2）BFS，广度优先

class Solution {
    //BFS，广度优先
    public TreeNode invertTree(TreeNode root) {
        if(root == null) return root;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i=0; i<size; i++){
                TreeNode current = queue.poll();
                TreeNode temp = current.left;
                current.left = current.right;
                current.right = temp;                             
                if(current.left != null) queue.offer(current.left); 
                if(current.right !=null) queue.offer(current.right);
                //这两句顺序可以调换，因为queue的作用只是记录哪个TreeNode的左右子节点需要调换
            }            
        }
        return root;
    }
}

Leetcode 257. Binary Tree Paths. 【Easy】
Time: O(n), Space: O(n).
设置helper函数,用Recursive遍历root.left和root.right。

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> list = new ArrayList<>();
        if(root == null) return list;
        helper(list,root,"");
        return list;        
    }
    
    private void helper(List<String> list,TreeNode root, String path){
        if(root.left == null && root.right == null){  //判断是否为leaf，若是就加入list  
            list.add(path + root.val);    //三个if可以互换顺序。
        }
        if(root.left != null){
            helper(list,root.left, path + root.val + "->");  //遍历root.left
        }
        if(root.right != null){
            helper(list,root.right,path + root.val + "->"); //遍历root.right
        }
    }
}

Leetcode 112. Path Sum. 【Easy】
两种方法，
1)recursive。递归(递回). 归/回，翻译了re。

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null) return false;
        if(root.left == null && root.right == null){
            return root.val == sum;
        }
        return hasPathSum(root.left, sum-root.val) || hasPathSum(root.right,sum-root.val);
    }
}

Iterative，迭代。
缺点：改变了整个树所存储的数字。

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null) return false;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode cur = stack.pop();
            if(cur.left == null && cur.right == null){
                if(cur.val == sum){
                    return true;
                }
            } 
            if(cur.left != null){
                stack.push(cur.left);
                cur.left.val += cur.val; 
            }
            if(cur.right != null){
                stack.push(cur.right);
                cur.right.val += cur.val;
            }
        }
        return false;       
    }    
}

Leetcode 113. Path Sum II. 【Medium】
只能写recursive。设置了返回void的helper函数。注意其传入参数list是用来记录路径的

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) return res;
        helper(res, new ArrayList<>(), root, sum);
        return res;
    }
    
    private void helper(List<List<Integer>> res, List<Integer> list, TreeNode root, int sum){
        if(root == null) return;
        list.add(root.val);
        if(root.left == null && root.right == null){
            if(root.val == sum){
                res.add(new ArrayList<>(list));    
                //res.add(list)错误，因为list会不断删改。需要开辟新空间来存储add进去的list
            }
        }
        helper(res,list,root.left,sum-root.val);
        helper(res,list,root.right,sum-root.val);
        list.remove(list.size()-1);    //位置，在两个helper之后。可以看看discuss的答案(不如这个答案简便)
    }
}

Leetcode 129. Sum Root to Leaf Numbers. 【Medium】

class Solution {
    public int sumNumbers(TreeNode root) {
        return helper(root, 0);            
    }
    
    private int helper(TreeNode root, int sum){
        if(root == null) return 0;
        if(root.left == null && root.right == null){
            return sum*10 + root.val;
        }
        return helper(root.left, sum*10+root.val) + helper(root.right,sum*10+root.val);
    }
}

Leetcode 129. Sum Root to Leaf Numbers. 【Medium】
只能写recursive。

class Solution {
    public int sumNumbers(TreeNode root) {
        return helper(root, 0);            
    }
    
    private int helper(TreeNode root, int sum){
        if(root == null) return 0;
        if(root.left == null && root.right == null){
            return sum*10 + root.val;
        }
        return helper(root.left, sum*10+root.val) + helper(root.right,sum*10+root.val);
    }
}

Leetcode 298. Binary Tree Longest Consecutive Sequence. 【Medium】
只能写recursive。设置helper()函数，两种做法：设/不设全局变量

class Solution {
    //做法1，不设置全局变量，helper返回int        
    public int longestConsecutive(TreeNode root) {
        if(root == null) return 0;
        return helper(root, root.val,0,0); //让第一次root经过步骤if(root.val == target)
    }
    
    private int helper(TreeNode root, int target, int res, int cur){
        if(root == null) return res;
        if(root.val == target){
            cur++;
            //res = Math.max(res,cur); 放这里也可以，便于理解
        } else {
            cur = 1;
        }
        res = Math.max(res,cur);
        return Math.max(
            helper(root.left, root.val+1,res,cur), 
            helper(root.right,root.val+1,res,cur)
        );
    }
    
    //做法2，设立一个全局变量attribute, helper()函数返回void
    private int res = 0;    
    public int longestConsecutive(TreeNode root) {
        if(root == null) return 0;
        helper(root,0,root.val);
        return res;
    }
    
    private void helper(TreeNode root, int cur, int target){
        if(root == null) return;
        if(root.val == target){
            cur++;
        } else {
            cur = 1;
        }
        res = Math.max(res, cur);
        helper(root.left, cur, root.val+1);
        helper(root.right,cur, root.val+1);
    }  
}

Leetcode 111. Minimum Depth of Binary Tree. 【Easy】
Time: o(n), Space: O(n)
题意：找最浅的depth。第一想法是BFS，但BFS的iterative形式太麻烦(做法3)。用recursive的形式做，最简单(做法1)。

class Solution {
    
    //做法1
    public int minDepth(TreeNode root) {
        if (root == null)   return 0;
        if (root.left == null)  return minDepth(root.right) + 1;
        if (root.right == null) return minDepth(root.left) + 1;
        return Math.min(minDepth(root.left),minDepth(root.right)) + 1;        
    }
    
    //做法2
    public int minDepth(TreeNode root) {
        if(root == null) return 0;
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        return (left == 0 || right == 0) ? left + right + 1: Math.min(left,right) + 1;       
    }
    
    //做法3，BFS
    public int minDepth(TreeNode root) {
        if (root == null)   return 0;
        int depth = 1;
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode curr = queue.poll();
                if (curr != null && curr.left == null && curr.right == null;   return depth; // leaf node
                if (curr.left != null)  queue.offer(curr.left);
                if (curr.right != null) queue.offer(curr.right);
            }
            depth += 1;
        }
        return -1;
    }          
}

Leetcode 104. Maximum Depth of Binary Tree. 【Easy】
两种递归方式。做法1是直接return调用递归，做法2是分为left和right，这种处理是很常见的

class Solution {
    // //做法1
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right))+1;
    }
    //做法2
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        int left = maxDepth(root.left)+1;
        int right = maxDepth(root.right)+1;
        return Math.max(left,right);
    }        
}

Leetcode 110 Balanced Binary Tree. 【Easy】

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        return helper(root) != -1;
    }
    private int helper(TreeNode root){
        if(root == null) return 0;
        int left = helper(root.right);
        int right = helper(root.left);
        if(Math.abs(right-left)>1 || left == -1 || right == -1){
            return -1;
        }
        return Math.max(left,right)+1;
    }
    
}

Leetcode 124. Binary Tree Maximum Path Sum. 【Hard】
后序遍历的典型做法，分为left和right；设置全局变量来记录res，参考298

class Solution {
    //法1，设置全局变量(global variable, java的attribute)
    int res;
    public int maxPathSum(TreeNode root) {
        if(root == null) return 0;
        res = Integer.MIN_VALUE;
        helper(root);
        return res;
    }
    private int helper(TreeNode root){
        if(root == null) return 0;
        int left = Math.max(0, helper(root.left));
        int right = Math.max(0,helper(root.right));
        res = Math.max(res, left+right+root.val);
        return Math.max(left, right) + root.val;
    }
    //法2，无attribute情况(global variable)
    //不能设置int max,是因为java方法的传入参数是int时是值传递，int[]是地址传递。int是八大primitive data types之一, 其他都是non primitive data types
    public int maxPathSum(TreeNode root) {
        if(root == null) return 0;
        int[] max = new int[1];
        max[0] = Integer.MIN_VALUE;
        helper(root,max);
        return max[0];
    }
    private int helper(TreeNode root, int[] max ){
        if(root == null) return 0;
        int left = Math.max(0, helper(root.left,max));
        int right = Math.max(0,helper(root.right,max));
        max[0] = Math.max(max[0], left+right+root.val);
        return Math.max(left, right) + root.val;
    }       
}

Leetcode 250. Count Univalue Subtrees. 【Medium】
后序遍历的典型做法，分为left和right；设置全局变量来记录res，参考124，298


class Solution {
//设置全局变量：int res.
    int res;
    public int countUnivalSubtrees(TreeNode root) {
        //res = 0;    // 如果是 int res = 0; 就出错，因为这样做会新开辟区间，方法里的res会是零值。
        //或者不初始化也行。
        helper(root);
        return res;
    }
    private boolean helper(TreeNode root){
        if(root == null) return true;
        boolean left = helper(root.left);
        boolean right = helper(root.right);
        if(left && right){
            if(root.left != null && root.val != root.left.val){
                return false;
            }
            if(root.right != null && root.val != root.right.val){
                return false;                
            }
            res++;
            return true;
            
        } 
        return false;
    }

//不设置变量，用int[] 来记录结果
public class Solution {
    public int countUnivalSubtrees(TreeNode root) {
        int[] count = new int[1];
        helper(root, count);
        return count[0];
    }
    
    private boolean helper(TreeNode node, int[] count) {
        if (node == null) {
            return true;
        }
        boolean left = helper(node.left, count);
        boolean right = helper(node.right, count);
        if (left && right) {
            if (node.left != null && node.val != node.left.val) {
                return false;
            }
            if (node.right != null && node.val != node.right.val) {
                return false;
            }
            count[0]++;
            return true;
        }
        return false;
    }
}
}

Leetcode 366. Find Leaves of Binary Tree 【Medium】
输出叶子节点。三种遍历方式，显然要选后续遍历。关键是设置int level，helper函数返回level，从而知道放入list的位置。

class Solution {
    public List<List<Integer>> findLeaves(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        helper(res, root);
        return res;
    }
    private int helper(List<List<Integer>> res, TreeNode root){
        if(root == null) return -1;
        int left = helper(res, root.left);
        int right = helper(res, root.right);
        int level = Math.max(left,right)+1;
        if(res.size() == level){
            res.add(new ArrayList());
        }
        res.get(level).add(root.val);
        root.left = null;
        root.right = null;
        return level;              
    }
}

Leetcode 337. House Robber III 【Medium】
比较奇数层和偶数层哪个较大。用Recursive递归写。

class Solution {
    public int rob(TreeNode root) {
        if(root == null) return 0;
        int val = 0; 
        if(root.left != null){
            val += rob(root.left.left) + rob(root.left.right);
        }
        if(root.right != null){
            val += rob(root.right.left) + rob(root.right.right);
        }
        return Math.max(root.val + val, rob(root.left)+rob(root.right));
    }
}

Leetcode 107. Binary Tree Level Order Traversal II 【Easy】
将102代码稍作改变，改为在res第0位插入。两种方法。
方法1. iterative.

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while( !queue.isEmpty()){
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            for(int i=0; i<size; i++){
                TreeNode cur = queue.poll();
                list.add(cur.val);
                if(cur.left != null)queue.add(cur.left);
                if(cur.right != null)queue.add(cur.right);
            }
            res.add(0,list);
        }
        return res;
    }

方法2，Recursive，更好。

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        //if(root == null) return res;
        helper(root,res,0);
        return res;
    }
    
    private void helper(TreeNode root, List<List<Integer>> res, int level){
        if(root == null) return;
        if(level == res.size()){
            res.add(0,new ArrayList<>()); //HashMap有put()方法
        }
        res.get(res.size()-level-1).add(root.val);
        helper(root.left,res,level+1);
        helper(root.right,res,level+1);        
    }
}

Leetcode 103. Binary Tree Zigzag Level Order Traversal. 【Medium】
依赖于层数level的题，都可以考虑recursive，设置helper函数，给helper函数传入int level，返回void.

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) return res;
        helper(res,root,0);     
        return res;                           
    }
    private void helper(List<List<Integer>> res, TreeNode root, int level){
        if(root == null) return;
        if(level == res.size()){
            res.add(new ArrayList<>());
        }
        //List<Integer> list = res.get(level); 也可以
        if(level %2 == 0){
            res.get(level).add(root.val);
        } else {
            res.get(level).add(0,root.val);
        }
        helper(res,root.left,level+1);
        helper(res,root.right,level+1);       
    }
    因为List是non primitive data types,所以对于list的直接修改会影响到res.get(level)
    而int a=1; int b=a; b+=2; 得到的是b=3,a=1,因为int是八大primitive data types之一。
}

法2，iterative方法。

    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 zigzag = false;
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            for(int i=0; i<size;i++){
                TreeNode cur = queue.poll();
                if(zigzag){  //odd, from right to left
                    list.add(0,cur.val);
                } else { //even, from left to right
                    list.add(cur.val);
                }
                if(cur.left != null) queue.add(cur.left);
                if(cur.right != null) queue.add(cur.right);
            }
            zigzag = !zigzag;
            res.add(list);
        }
        return res;       
    }

Leetcode 199. 199. Binary Tree Right Side View. 【Medium】
Tree的iterative方法，是BFS,每层遍历; recursive方法，是DFS,首先达到最底层的left和right。

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList();
        if(root == null) return res;
        helper(root,res,0);
        return res;
    }
helper1方法
    private void helper(TreeNode root, List<Integer> res, int level){
        if(root == null) return;
        if(level == res.size()){
            res.add(root.val);
        } else {
            res.set(level,root.val);
        }
        helper(root.left,res,level+1);
        helper(root.right,res,level+1);
    }  
helper2方法    
    private void helper(TreeNode root, List<Integer> res, int level){
        if(root == null) return;
        if(level == res.size()){
            res.add(root.val);
        } 
        helper(root.right,res,level+1);
        helper(root.left,res,level+1);
    }     
}

BFS，iterative方法。

    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i=0; i<size; i++){
                TreeNode cur = queue.poll();
                if(i==0) res.add(cur.val);
                if(cur.right != null) queue.add(cur.right);
                if(cur.left != null) queue.add(cur.left);
            }
            
        }
        return res;
    }

BST(Binary Search Tree) 二叉搜索树
性质: 左子树比parent小，右子树比parent大。

Leetcode 98. Validate Binary Search Tree. 【Medium】
只比较：root和root.left, root和root.right，是不行的，因为没有实现跨行比较。比如：
6
/ \
2 10
/ \
1 12
12比2大，出现在6的left部分。由此可见，必须要设置min和max。
只要设置了min和max，就反映出BST的实质，即root是左边的max，右边的min。注意：BT二叉树和BST二叉搜索树的不同，二叉树没有顺序。
【二叉搜索树，按照中序遍历，是递增的】

class Solution {
    public boolean isValidBST(TreeNode root) {
        if(root == null) return true;
        return helper(root,null,null);
    }
    private boolean helper(TreeNode root, Integer min, Integer max){ //若是int a, int b就错了
        if(root == null) return true;
        if(min != null && root.val <= min) return false;
        if(max != null && root.val >= max) return false;
        return helper(root.left,min,root.val) && helper(root.right,root.val,max);
    }
    
    //Integer a = null; 正确。int b = null; 报错    
    原因：
    In Java, int is a primitive type and it is not considered an object. Only objects can have a null value. 
    int 是基本数据类型，不可为null。Integer是一个object，可以为null    
}

Leetcode 235. Lowest Common Ancestor of a Binary Search Tree. 【Easy】
由于从根结点root开始遍历，最坏情况下root就是答案，所以可以设置else的条件，而不考虑例子中0，2，7的情况。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root.val < p.val && root.val < q.val){
            return lowestCommonAncestor(root.right,p,q);
        } else if(root.val > q.val && root.val > p.val){
            return lowestCommonAncestor(root.left,p,q);
        } else {
            return root;
        }
    }
}

Leetcode 236. Lowest Common Ancestor of a Binary Tree. 【Medium】
用后续遍历，left和right，再对left和right的结果进行判断。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;
        if(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){ //而不是 root.left != null && root.right != null
            return root;
        } else if(left != null){
            return left;
        } else if (right != null){
            return right;
        } else {
            return null;
        }
        //后三个else if 可换为： return left == null ? right : left;
    }
}

Leetcode 108. Convert Sorted Array to Binary Search Tree. 【Easy】
二分法思想 + recursive，创建新TreeNode cur, 并对cur.left和cur.right 赋值。

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums == null || nums.length == 0) return null;
        return helper(nums,0,nums.length-1);
    }
    private TreeNode helper(int[] nums, int left, int right){
        if(left > right) return null;
        int mid = (right - left)/2 + left;
        TreeNode cur = new TreeNode(nums[mid]);
        cur.left = helper(nums,left, mid-1);
        cur.right = helper(nums,mid+1,right);
        return cur;        
    }
}

Leetcode 109. Convert Sorted List to Binary Search Tree. 【Medium】
参考108，只是修改为ListNode，Listnode中点不可以直接知道，需要用slow和fast遍历。
The time complexity of the solution is O(n logn) since you have to traverse the sub-list in each recursive call.

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null) return null;
        return helper(head, null);
    }
    private TreeNode helper(ListNode head, ListNode tail){
        if(head == tail) return null;
        ListNode slow = head;
        ListNode fast = head;
        while(fast != tail && fast.next != tail){ //难点：不能将tail改为null，因为用了recursive，null只对第一次从head到tai有用
            slow = slow.next;
            fast = fast.next.next;
        }
        TreeNode mid = new TreeNode(slow.val); //root
        mid.left = helper(head, slow);
        mid.right = helper(slow.next, tail);
        return mid;   //return root
    }
}

leetcode 173. Binary Search Tree Iterator. 【Medium】
明显需要中序遍历+iterative (next()返回int, 不能用recursive写法)。参考94, 中序遍历的两个iterative写法。
中序遍历，不用current的写法：(自定义,写一个recursive方法)

class BSTIterator {
    
    private Stack<TreeNode> stack; 
    public BSTIterator(TreeNode root) {
        stack = new Stack<>();
        pushAll(root);
    }
    
    private void pushAll(TreeNode node){
        while(node != null){
            stack.push(node);
            node = node.left;
        }
    }   
    /** @return the next smallest number */
    public int next() {
        TreeNode cur = stack.pop();
        pushAll(cur.right);
        return cur.val;
    }
    
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stack.isEmpty();
    }

中序遍历，用current的写法：

    //法2
    private Stack<TreeNode> stack; 
    private TreeNode cur;
    public BSTIterator(TreeNode root) {
        cur = root;
        stack = new Stack<>();
    }
    
    /** @return the next smallest number */
    public int next() {
        while( cur != null){
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        int val = cur.val;
        cur = cur.right;
        return val;
    }
    
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        if(!stack.isEmpty() || cur != null) return true;
        return false;
    }

leetcode 230. Kth Smallest Element in a BST. 【Medium】
用recursive方法，中序遍历inOrder。设置了两个attribute: count和int来记录。注意 count-- 是在helper(left)和helper(right)中间，从而实现中序遍历。

class Solution {
    private int count;
    private int res;
    public int kthSmallest(TreeNode root, int k) {
        count = k;
        helper(root);        
        return res;
    }
    private void helper(TreeNode root){
        if(root == null) return;
        helper(root.left);
        count--;
        if(count == 0) res = root.val;
        helper(root.right);
    };    
}

或者换为 count++的形式，更容易理解。

int count = 0;
int result;

public int kthSmallest(TreeNode root, int k) {
    traverse(root, k);
    return result;
}

public void traverse(TreeNode root, int k) {
    if(root == null) return;
    traverse(root.left, k);
    count ++;
    if(count == k) result = root.val;  //count++后得到的count正是root的排名，所以if()放在了left和right之间
    traverse(root.right, k);       
}

iterative的写法：

    public int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<>();
        int count = 0;
        TreeNode cur = root;
        while(!stack.isEmpty() || cur != null){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            count++;
            if(count == k) return cur.val;
            cur = cur.right;            
        }
        return Integer.MIN_VALUE;               
    }

Leetcode 297. Serialize and Deserialize Binary Tree. 【Hard】
recursive方法更简单。
Recursive方法

    //Recursive 方法
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        buildString(root, sb);
        return sb.deleteCharAt(sb.length()-1).toString();                
    }
    private void buildString(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append("null").append(",");
        } else {
            sb.append(node.val).append(",");
            buildString(node.left, sb);
            buildString(node.right,sb);
        }
    }
        
    public TreeNode deserialize(String data) {
        Deque<String> nodes = new LinkedList<>();
        nodes.addAll(Arrays.asList(data.split(",")));
        return buildTree(nodes);
    }
    
    private TreeNode buildTree(Deque<String> nodes) {
        String val = nodes.poll();
        if (val.equals("null")){
            return null;
        } else {
            TreeNode node = new TreeNode(Integer.valueOf(val));
            node.left = buildTree(nodes);
            node.right = buildTree(nodes);
            return node;
        }
    }

Iterative方法

public class Codec {
    //
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) return "";
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i=0; i<size; i++){
                TreeNode cur = queue.poll();
                if(cur == null){
                    sb.append("null,");
                } else {
                    sb.append(cur.val+",");
                    queue.offer(cur.left);
                    queue.offer(cur.right);
                }                
            }
        }
        // String res = sb.toString();
        // return res.substring(0,res.length()-1); 删除最后一个逗号
        return sb.deleteCharAt(sb.length()-1).toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null || data.length() == 0) return null;
        String[] str = data.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(str[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int i = 0;
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if(!str[i+1].equals("null")){
                cur.left = new TreeNode(Integer.parseInt(str[i+1]));
                queue.add(cur.left);
            }
            if(!str[i+2].equals("null")){
                cur.right = new TreeNode(Integer.parseInt(str[i+2]));
                queue.add(cur.right);
            }
            // if(i+2>=str.length()) break;不用判断，因为最终有while条件来判断
            i+=2;
        }
        return root;        
    }
}

Leetcode 285. Inorder Successor in BST. 【Medium】
找出大于目标的最小值.
iterative方法

class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode res = null;
        while(root != null){
          if(root.val <= p.val){
              root = root.right;
          } else {
              res = root;
              root =root.left;
          }
        }
        return res;
    }    
}

recursive方法

        if(root == null) return null;
        if(root.val <= p.val){
            return inorderSuccessor(root.right,p);
        } else {
            TreeNode temp = inorderSuccessor(root.left,p);
            return temp == null ? root : temp;
        }

Leetcode 270. Closest Binary Search Tree Value. 【Easy】
Iterative和Recursive两种方法。
Iterative方法。Time: O(n), Space: O(1).

class Solution {
    public int closestValue(TreeNode root, double target) {
        int res = root.val;
        while(root != null){
            if(Math.abs(target-root.val)<Math.abs(target-res)){
                res = root.val;
            };
            root = root.val > target? root.left:root.right;
        }
        return res;
    }
}

Recursive方法。Time: O(n), Space: O(n).

    public int closestValue(TreeNode root, double target) {
        return helper(root,target,root.val);            
    }
    private int helper(TreeNode root,double target,int val){
        if(root == null) return val;
        if(Math.abs(target-root.val)<Math.abs(target-val)){
            val = root.val;
        }
        if(root.val<target){
            return helper(root.right,target,val);
        } else if(root.val>target){
            return helper(root.left,target,val);
        }
        return val;
    }

Leetcode 272. Closest Binary Search Tree Value II. 【Hard】
Time: O(n) 的做法：

class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        List<Integer> res = new ArrayList<>();
        helper(root,target,k,res);
        return res;
    }
    private void helper(TreeNode root, double target, int k, List<Integer> res){
        if(root == null) return;
        helper(root.left,target,k,res);
        if(res.size()==k){
            if(Math.abs(target-root.val)<Math.abs(target-res.get(0))){
                res.remove(0);
                res.add(root.val);
            } 
        } else {
            res.add(root.val);
        }        
        helper(root.right,target,k,res);       
    }
}

FollowUp: 能不能优于O(n)?
做法：
时间复杂度：O(log n + k) 【有争议，有人认为worse case是O(klogn)】

class Solution {
    
    //https://leetcode.com/problems/closest-binary-search-tree-value-ii/discuss/70503/O(logN)-Java-Solution-with-two-stacks-following-hint
    
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        Stack<TreeNode> succ = new Stack<>(); //凡是不确定用Stack还是Queue，都用Deque
        Stack<TreeNode> pred = new Stack<>();
    
        inOrderTraversal(root,false,target,succ);   //Time: O(logn)
        inOrderTraversal(root,true,target,pred);    //Time: O(logn)
    
        List<Integer> result = new ArrayList<>();
    
        for(int i = 0; i<k; i++){
            if(succ.size()==0){
                result.add(getNext(pred,true));
            }else if(pred.size()==0){
                result.add(getNext(succ,false));
            }else{
                if(Math.abs(target-succ.peek().val)<Math.abs(target-pred.peek().val)){ //succ.peek()是cucc中最靠近target的,高个子中的最小值;pred.peek()是pred中最靠近target的矮个子中的最大值
                    result.add(getNext(succ,false));
                }else{
                    result.add(getNext(pred,true));
                }
            }
        }
        return result;
    }
    private void inOrderTraversal(TreeNode root, boolean isPred, double target, Stack stack){
        while(root != null){
            if((!isPred && root.val>=target) || (isPred && root.val<target)){ // >=和< 或者 >和<=
                stack.push(root);
                root = isPred?root.right:root.left;
            }else{
               root = isPred?root.left:root.right;
            }            
            二选一
            // if(isPred && root.val == target){
            //     stack.push(root);
            //     break;
            // } else if((!isPred && root.val>target) || (isPred && root.val<target)){
            //     stack.push(root);
            //     root = isPred?root.right:root.left;
            // } else {
            //    root = isPred?root.left:root.right;                
            // }
            //目标是6，succ加入顺序是：由大到小接近6(不是从最大的数开始而是接近root的大于6的数开始)；pred加入顺序是由小到大接近6(不是从最小的数开始)
        }
    }

//getNext() 就是把stack的最上层(最靠近target的TreeNode值)pop出来，(然后把这个TreeNode的左边(若是pred)或右边(若是succ)加入stack中，
// 目的是把记录到stack中的靠近target的值的集合变得更大，从而为k值作准备
// 因为我们是不知道k值和stack中的值的数量的比较，若k很大，例如k和整个树的节点数量差不多，
// 那么我们就要在inOrderTraversal()得到的两个stack的基础上(最多只能遍历一半节点,从而达到O(logn)的时间复杂度)，一直增加之前没遍历到的节点.
    private Integer getNext(Stack<TreeNode> stack, boolean isPred){ 
        TreeNode curr = stack.pop();
        Integer val = curr.val;
        curr = isPred?curr.left:curr.right;
        while(curr!=null){
           stack.push(curr);
           curr = isPred? curr.right: curr.left;
        }
        return val;
    }

参考题目658, 题目有点类似。
但本题若转为list，那么inorder的时间复杂度已经是O(n)。所以达不到O(logn).

inorder and binary search, similar to Leetcode 658,  find k closest values to target in a sorted array

class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        List<Integer> list = new ArrayList();
        inorder(root, list);
        int l = 0, r = list.size()-k;
        while(l<r){
            int mid = l+(r-l)/2;
            double left = (double)list.get(mid);
            double right = (double)list.get(mid+k);
            // find optimal interval here
            if(Math.abs(left-target)>Math.abs(right-target)){
                l++;
            }else{
                r--;
            }
        }
        List<Integer> res = new ArrayList();
        for(int i=l;i<l+k;i++){
            res.add(list.get(i));
        }
        return res;
    }

    public void inorder(TreeNode node, List<Integer> res){
        if(node==null) return ;
        inorder(node.left, res);
        res.add(node.val);
        inorder(node.right,res);
    }
}

Leetcode 99. Recover Binary Search Tree. 【Hard】
【二叉搜索树，按照中序遍历，是递增的.】
Recursive：
用三个class attribute: prev, first, second记录，在recursive 的helper()中中序遍历。
https://leetcode.com/problems/recover-binary-search-tree/discuss/32562/Share-my-solutions-and-detailed-explanation-with-recursiveiterative-in-order-traversal-and-Morris-traversal

If we found an incorrect pair where prev.val > curr.val, how do we know which node is the incorrect one? The answer is it depends on whether we have found incorrect node before. So What is that? 怎么区分那个是incorrect node？

Since we get two elements that are swapped by mistake, there must be a smaller TreeNode get a larger value and a larger TreeNode get a smaller value.
Their value are swapped, but the incorrect smaller node is still in smaller tree and incorrect larger node is still in larger tree. So we will visit the incorrect smaller node first, and this node will be detected when we compare its value with next.val, i.e. when it is treated as prev node. The incorrect larger node will be detected when we compare its value with prev.val. We don't know if it is close or not close to incorrect smaller node, so we should continue search BST and update it if we found another incorrect node.
因为我们是将一个smaller node 和一个larger node 换。
(1)当我们找到第一个 prev >= current, incorrect node 肯定是prev。发生错误的必然是larger node (prev位置) 和smaller node的下一个节点(current位置)。
(2)对于第二个 prev >= current, incorrect node 肯定是 root。发生错误的是 larger node的上一个节点(prev位置) 和 smaller node (current位置) 。

Therefore if it is the first time we found an incorrect pair, the prev node must be the first incorrect node.
If it is not the first time we found an incorrect pair, the curr node must be the second incorrect node, though we may have corner case that two incorrect nodes are in same pair.
当然也有可能是 prev >= current 只有一次，所以才有 second = root 。

class Solution {
    TreeNode prev = null;
    TreeNode first = null;
    TreeNode second = null;
    public void recoverTree(TreeNode root) {
        inOrder(root);
        int temp = first.val;
        first.val = second.val;
        second.val = temp;        
    }
    public void inOrder(TreeNode root){ 
        if(root == null) return;
        //search left tree
        inOrder(root.left);
//incorrect smaller node is always found as prev node
//incorrect larger node is always found as curr(root) node
        if(prev != null && prev.val >= root.val){
            if(first == null){
                first = prev;
                second = root; //有可能就是这两个数
            } else {
                second = root; //进入这里说明first已经找到，并且root就是second
                //return; 写不写都行
            }
        }        
        prev = root;
        inOrder(root.right);
    }    
}

Iterative：思路是一样的。

    public void recoverTree(TreeNode root) {
        if(root == null) return;
        TreeNode prev = null;
        TreeNode first = null;
        TreeNode second = null;        
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(!stack.isEmpty() || cur != null){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            if(prev != null && prev.val >= cur.val){
                if(first == null){
                    first = prev;
                    second = cur;
                } else {
                    second = cur;
                }               
            }
            prev = cur;
            cur = cur.right;            
        }
        int temp = first.val;
        first.val = second.val;
        second.val = temp;   
        System.out.println(first.val + "/"+ second.val);            
    }

Leetcode-Tree

推荐阅读更多精彩内容