算法模板

  1. public void recur(int level, int param) {
  3.     //terminator
  4.     if (level > MAX_LEVEL) {
  5.         //process result
  6.         return ;
  7.     }
  8.     //process current logic
  9.     process(level, param);
  11.     //drill down
  12.     recur(level:level + 1,param);
  14.     //restore current status
  15. }

22.括号生成

226.翻转二叉树

98.验证二叉搜索树

297.二叉树的序列化与反序列化

Homework

236.二叉树的最近公共祖先

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

77.组合

47.全排列 II

刷题记录

二叉树的最大深度

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

226. 翻转二叉树

  1.     public TreeNode invertTree(TreeNode root) {
  2.         if(root == null){
  3.             return root;
  4.         }
  5.         TreeNode newLeft = invertTree(root.right);
  6.         TreeNode newRight = invertTree(root.left);
  8.         root.left = newLeft;
  9.         root.right = newRight;
  10.         return root;
  11.     }

98. 验证二叉搜索树

  1.     public boolean isValidBST(TreeNode root) {
  2.         return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
  3.     }
  4.     public boolean isValidBST(TreeNode node,long lower,long upper) {
  5.        if(node == null){
  6.            return true;
  7.        }
  8.        if(node.val <= lower || node.val >= upper){
  9.            return false;
  10.        }
  11.        return isValidBST(node.left,lower,node.val) && isValidBST(node.right,node.val,upper);
  12.     }

22. 括号生成

  1.     private List<String> ans;
  2.     public List<String> generateParenthesis(int n) {
  3.         ans = new ArrayList<>();
  4.         _travel(0,0,n,"");
  5.         return ans;
  6.     }
  8.     private void _travel(int left, int right, int n, String s) {
  9.         if(left==n&&right==n){
  10.             ans.add(s);
  11.             return;
  12.         }
  13.         if(left<n){
  14.             _travel(left+1,right,n,s+"(");
  15.         }
  16.         if(right<left){
  17.             _travel(left,right+1,n,s+")");
  18.         }
  19.     }

77. 组合

 private List<List<Integer>> res = null;
    private List<Integer> temp = null;

    public List<List<Integer>> combine(int n, int k) {
        res = new ArrayList<>();
        temp = new ArrayList<>();
        dfs(1, n, k);
        return res;
    }

    private void dfs(int cur, int n, int k) {
        if ((temp.size() + (n - cur + 1)) < k) {
            return;
        }
        if (temp.size() == k) {
            res.add(new ArrayList<>(temp));
            return;
        }

        temp.add(cur);
        dfs(cur + 1, n, k);
        temp.remove(temp.size() - 1);
        dfs(cur + 1, n, k);
    }