Binary Tree Traversal (Recursive)

Leave a comment

December 11, 2016 by oneOokay

  • Inorder
  • Preorder
  • Postorder
  1. 输出会是一个List或者String类型的method: List/String XXX(TreeNode root);
  2. 这个函数本身并不能够作为recursion method:如果本身作为recursion method的话就会变成:
 List XXX(TreeNode root){
 ...
 ...
 return XXX(node);
}

XXX method本身的return的结果是下一个recursion要对其进行操作的,这里的XXX只读入一个TreeNode,并不能够达成目的。

所以用一个helper method来做recursion ,经过该helper method,最终build answer。

  • 可以用一个private 变量来存ans(见完整代码)
  • 也可把ans作为helper method的一个变量:
private void helper(TreeNode node, List<Integer> ans){}

preorder/inorder/postorder只需要对helper函数里面的helper(node.left),helper(node.right),ans.add(node.val)进行相应调换即可。

public class Solution {
    private List ans;
    public List inorderTraversal(TreeNode root) {
        ans = new ArrayList();
        if (root == null){
            return ans;
        }
        
        helper(root);
        return ans;
    }
    
    private void helper(TreeNode node){
        if (node == null){
            return;
        }
        helper(node.left);
        ans.add(node.val);
        helper(node.right);
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: