3

我正在尝试解决这个问题https://oj.leetcode.com/problems/binary-tree-preorder-traversal/，即使用递归解决方案进行前序遍历。

编辑：整个代码：

import java.util.ArrayList;
import java.util.List;

public class Solution {

    public class TreeNode {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode(int x) { val = x; }
    }
     static List<Integer> res = new ArrayList<Integer>();
     public List<Integer> preorderTraversal(TreeNode root) {
            if(root == null){
                return new ArrayList<Integer>();
            }
            res.add(root.val);
            if(root.left != null){
                res.add(preorderTraversal(root.left));
            }
            if(root.right != null){
                res.add(preorderTraversal(root.right));
            }
            return res;
      }
}

由于以下原因，我有错误的答案：

Input:  {1,2}
Output:     [1,1,2]
Expected:   [1,2]

有人可以告诉我如何解决这个问题吗？

编辑：我没有main()方法或单元测试。如果您打开我发布的链接，您会看到这是在线评审系统。

4

7 回答 7

4

问题是在每个递归循环中，您将整个数组再次添加到最终结果中。

例如，给定以下树：

  1
 /
2

您的第一次迭代将 1 添加到“res”变量中。问题是当它到达这条线时：

res.add(preorderTraversal(root.left));

然后它递归地调用左侧。preorderTraversal 将返回 res 数组，即 [1,2]。因此，当 [1,2] 被添加到 res （这是 [1]，记得吗？），然后你得到 [1,1,2]。

这是应该工作的代码：

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<Integer>();

    if(root == null){
        return result;
    }

    result.add(root.val);
    if(root.left != null){
        result.addAll(preorderTraversal(root.left));
    }
    if(root.right != null){
        result.addAll(preorderTraversal(root.right));
    }

    return result;
}
于 2014-07-26T09:43:27.997 回答
2

对于左右节点，只需preorderTraversal递归调用，它会将值添加到res. 使用这些递归调用的结果进行调用是错误的add/addAll。res

public class Solution {
     List<Integer> res = new ArrayList<Integer>();
     public List<Integer> preorderTraversal(TreeNode root) {
            if(root == null){
                return new ArrayList<Integer>();
            }
            res.add(root.val);
            if(root.left != null){
                preorderTraversal(root.left);
            }
            if(root.right != null){
                preorderTraversal(root.right);
            }
            return res;
      }
}

这个解决方案有一个小问题——res保留以前调用的值，所以preorderTraversal在同一个实例上多次调用可能会返回不正确的结果。这是一个没有这个缺点的解决方案：

public class Solution {
     public List<Integer> preorderTraversal(TreeNode root) {
            List<Integer> res = new ArrayList<Integer>();
            preorderTraversal(root, res);
            return res;
      }
      private void preorderTraversal(TreeNode node, List<Integer> res) {
          if (node != null) {
              res.add(node.val);
              preorderTraversal(node.left, res);
              preorderTraversal(node.right, res);
          }
      }
}
于 2014-07-26T09:56:40.310 回答
1

试试这个方法代码：

public List<Integer> preorderTraversal(TreeNode root) {
        if(root == null){
            return new ArrayList<Integer>();
        }
        res.add(root.val);
        if(root.left != null){
            res = preorderTraversal(root.left);
        }
        if(root.right != null){
            res = preorderTraversal(root.right);
        }
        return res;
   }

顺便说一句，你res.add在递归中做。你应该res=在里面做。

于 2014-07-26T09:43:52.757 回答
1

一个可行的解决方案：

import java.util.ArrayList;
import java.util.List;



class TreeNode 
{
      int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
 }

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) 
    {
       ArrayList<Integer> res = new ArrayList<Integer>();

        if(root == null)
            return res;
        else res.add(root.val);

        if(root.left != null)
        {
            res.add(root.left.val);
            preorderTraversal(root.left);
        }

        if(root.right != null)
        {
            res.add(root.right.val);
            preorderTraversal(root.right);
        }


        return res;    
    }
}

public class TreeTest
{


    public static void main(String[] args)
    {

        Solution c = new Solution();

        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);

        //Link the nodes of the tree
        t1.left = t2;
        t1.right = t3;


        List<Integer> list = c.preorderTraversal(t1);

        System.out.println(list);
    }
}
于 2014-07-26T10:16:08.623 回答
0

由于您还没有发布完整的代码输入是如何完成和输出是如何产生的，所以很难说。对于前序遍历，它应该是这样的。

 void traverse(TreeNode node){
   if(node != null){
      res.add(node.val);
      traverse(root.left);
      traverse(root.right);
    }
}
于 2014-07-26T09:48:18.873 回答
0 
public ArrayList<E> getPreOrderTraversal() {
    return getPreOrderTraversal(root);
}

private ArrayList<E> getPreOrderTraversal(Node tree) {
    ArrayList<E> list = new ArrayList<E>();

    if (tree != null) {
        list.add((E) tree.value);
        list.addAll(getPreOrderTraversal(tree.left));
        list.addAll(getPreOrderTraversal(tree.right));
    }

    return list;
}
于 2017-08-20T21:08:10.887 回答
0

一个可行且被 LeetCode 接受的解决方案：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        return preOrderTraversalInternal(root, list);
    }
    private List<Integer> preOrderTraversalInternal(TreeNode root, List<Integer> list){
    if(root == null) return list;
    list.add(root.val);
    if(root.left != null){
      preOrderTraversalInternal(root.left, list);
    }
    if(root.right != null){
      preOrderTraversalInternal(root.right, list);
    }
    return list;
  }
}
于 2020-05-02T06:10:00.093 回答