Binary Tree Preorder Traversal,理解不这里的recursion啊

原题是这样的，Given a binary tree, return the preorder traversal of its nodes' values.

我的solution是这样的，我不能理解的是每次这个method都要create a new arrayList, 那结果不是RETURN的最后一个加到这个LIST里面的元素吗？其他的都元素是不是都没有被加进去？
public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        if(root==null) return result;
        result.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return result;
    }
}

你的方法返回的是【1】不是【3】，因为你等于下面的做了没返回来
在你的方法上稍微改一下，就可以返回全部

1. public class Solution {
   
2. public List<Integer> preorderTraversal(TreeNode root) {
   
3. List<Integer> result = new ArrayList<Integer>();
   
4. if(root==null) return result;
   
5. result.add(root.val);
   
6. result.addAll(preorderTraversal(root.left));
   
7. result.addAll(preorderTraversal(root.right));
   
8. return result;
   
9. }
   
10. }

复制代码

最后，同意二楼的意见，，去查查大牛怎么解的吧

不知道表达清楚没有，例如一个binary search tree {1,2,3}, 我的solution应该return 的是[3].

每次都new一个arraylist应该不对吧 我感觉应该是把arraylist放在你recursive的方法里 每次往里面加
至少方法的definition应该是 preOrder(TreeRoot root, List list)
同学习recursive 觉得好抽象

rsun 发表于 2014-11-4 11:35
你的方法返回的是【1】不是【3】，因为你等于下面的做了没返回来
在你的方法上稍微改一下，就可以返回全部 ...

解释得真的很清楚啊！一下就完全明白，谢谢！