• 时间复杂度 O(N) 通过O(1)的时间,把n的问题,变成了两个n/2的问题,复杂度是多少?

T(n) = 2T(n/2) + O(1)

= 2 * 2T(n/4) + O(1) + O(1)

=n + (1 + 2 + 4 +…+ n)

≈n + 2n

≈O(n)

• 二叉树的遍历算法 Traverse in Binary Tree Preorder / Inorder / Postorder 根左右 ／ 左根右 ／ 左右根

遍历二叉树就是一个递归方法，不同order只是你在哪个位置操作当前val而已。

     public void preorderHelper(ArrayList<Integer> result, TreeNode root) {
        result.add(root.val);
        if(root.left != null){
            preorderHelper(result, root.left);
        }
        if(root.right != null) {
            preorderHelper(result, root.right);
        }
    }

     public void inorderHelper(ArrayList<Integer> result, TreeNode root) {    
        if(root.left != null){
            inorderHelper(result, root.left);
        }
        result.add(root.val);
        if(root.right != null){
            inorderHelper(result, root.right);
        }
    }

• Traverse vs Divide Conquer

1.递归是实现方式,遍历和分治是可以用递归实现的算法思想

2.Result in parameter vs Result in return value

3.Top down vs Bottom up

4.Traverse的结果要改参数,返回参数. Divide conquer的结果直接return,是个更好的接口,因为给你什么参数最好不要改.

• 二叉搜索树 Binary Search Tree • Insert / Remove / Find / Validate