chen-w
7/26/2017 - 10:17 PM

DFS template

DFS template

// Template 1: Traverse

public class Solution {
  public void traverse (TreeNode root) {
    if (root == null) {
      return;
    }
    // do something with root
    traverse(root.left);
    // do something with root
    traverse(root.right);
    // do something with root
  }  
}

// Template2: divide and conquer

public class Solution {
  public Result Type traversal(TreeNode root) {
    // null or leaf
    if (root == null) {
      // do something and return;
    }
    
    // Divide
    ResultType left = traversal(root.left);
    ResultType right = traversal(root.right);
    
    // Conquer
    ResultType result = Merge from left and right;
    return result;
  }
}