首页 > itarticle > binary tree & divide and conquer

binary tree & divide and conquer

admin 11月 30, 2020 0

time complexity practice II

  • if using O(1) time could separate problem to O(n/2) problem => log n (binary tree)
  • if using O(1) time could separate problem to 2*O(n/2) problem => n logn (divide and conquer)
  • if using O(n) time could separate problem to 2* O(n/2) prblem => n

Traverse in Binary Tree

preorder/ inorder/postorder

  • preorder => root left right
  • inorder => left root right
  • postorder => left right root

recursion

  • 3 point of recursion: definition(do what, input waht), division, ending

divide and conquer

  • don’t need globe variable,using local variable to solve problem, need return value

DFS in binary Tree

preorder/ inorder/postorder

non-recursion vs traverse vs divde and conquer

non recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
//non traverse
  public List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
       List<Integer> preorder = new ArrayList<Integer>();
       
     if (root == null) {
      return preorder;
     }
        
     stack.push(root);
        while (! stack.empty()) {
            TreeNode node = stack.pop();
         preorder.add(node.val);
          if (node.right != null) {
                stack.push(node.right);
          }
            if (node.left != null) {
             stack.push(node.left);
           }
        }
        return preorder;
 }

traverse

1
2
3
4
5
6
7
8
 
public void preorder (TreeNode root,ArrayList<Integer> result) {
 if (root == null) {
      return;
  }
    result.add(root.val);
    preorder(root.left, result);
 preorder(root.right, result);
}

divide and conquer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
public ArrayList<Integer> pro(TreeNOde root) {
  ArrayList<Integer> result = new ArrayList<>();
   if (root == null) {
      return result;
   }
    ArrayList<Integer> left = pro(root.left);
  ArrayList<Integer> right = pro (root.right);
   
 result.add(root.val);
    result.addAll(left);
 result.addAll(right);
    
 return result;
}
  • difference of traverse and divide and conquer:
    • same globe variable, no return value in travserse, but have local return value in DC
    • top down in traverse, bottom up in divide and conquer
  • DC: local return and recursive call themself
  • traverse: globe return

introduce divide and conquer algorithm

  • divide and conquer is postorfer
  • relationship between whole tree and left child tree and right child tree, result relationship
1
 
class ResultType {int var1, var2;}
  • result type: return 2 value
    • balanced binary tree: not only need isBalanced, but also need the height of tree.

binary search tree

  • O()= node number * time for vevery node

understanding

  • recursion is the part of divide, traverse is using the way of division by recursion (and also using globe variable so return always is void)but not merge, DC is not only divide by recursion and record every time division(so we need local variable), but also find some way to merge the record together.
  • traverse: every recusion is focusing on root, operating root by globe variable.
  • divide and conquer(accumulating) using local variable, and every recursion is focusing on root and operating left and right,not left or right, left or right is the previous recursion record, passing value by previous return value, and attaching(accumulating) new value to the previous result, which is “merge”. thus it is bottom up.
    • divide and conquer:recursion corperating with local varaible and a accumulating way to merge left and right
    • multiple time using compare or if then globe variable+DC is more fit way than local variable
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能