首页 > itarticle > tree and recursion

tree and recursion

admin 11月 30, 2020 0

tree

Binary Tree

iterating tree
- by Level : BFS
- (what we have root, root.left, root.right)
- How to prove traverse is right
  - number right
  - order right
- order problem (where the root are)
  - pre order: root left right
  - in order
  - post order

recursion

recursive algorithm: self call self, big problme change to small problem
revcursive data structure: tree, linked list

complexity of recursion

time complexity: node calling =n; null calling = n+1; => 2n+1=>O(n)
space complexity: level number
- h = f(n) => n
- => log(n)

question summary

iterate all and set condition + globe variable: count node, sum of leaf node
iterate all and set condition + parameter variable(local variable):Max depth,
parameter variable(local variable) and other condition path of root to leaf: because every child has only 1 parent, so only one path can be declared,

understanding

recursion of tree

types of output
1. return int: can be a output,accumulate with other level of recursion
  - like List, List<List>, List
    
    question

How to solve accumulating of array or arraylist