Wednesday, January 6, 2016

Divide and Conquer: Preorder traversal of ternary tree


January 6, 2016
重温一道关于树遍历的题目, 在新年开始的第一个星期, 鼓励自己, 加油! 多写代码, 多练习.

Be humble, learn from her mistakes in 2015. Julia is learning how to solve "divide and conquer" - write a perfect recursive function - without bug in base case - recursive calls. 

Her lessons for recursive function design, divide and conquer solution in 2014, 2015:

1. Do the work for root node, but do not do the work for its children; In other words, a subproblem can be handled by a recursive call

2. Do not repeat base case 'if' clause - a checking afterwards in the recursive function call. Not necessary, except trying to use less stack. 

Julia, recursive function design is like dealing with a family - single parent with children; show the work how to handle root node, that is almost done. Let recursive function to take care of children, do not do the work for children nodes. For example, binary tree, 2 children, call recursive function twice; Ternary tree, 3 children, and then, use 3 recursive calls. 

Once again, "Do not do the work for children directly". 

Action items:
1. Work on Leetcode questions again and start with simple questions.

Binary Tree Preorder traversal of ternary tree
More reading about ternary tree:
  https://en.wikipedia.org/wiki/Ternary_search_tree

No comments:

Post a Comment