java - 在编写递归算法时使用全局变量与传递变量

Question

我有一种方法可以展平二叉搜索树。我有两种方法:

• 使用变量并传递它

import java.util.*;

public class BST {

private Node root;

private class Node {
    private int val;             // associated data
    private Node left, right;  // left and right subtree

    public Node(int val) {
        this.val = val;

    }
}   

public ArrayList<Integer> flattenTree(){

    ArrayList<Integer> list = new ArrayList<>();
    flattenTree(root, list);

    return list;
}

public void flattenTree(Node node, ArrayList<Integer> list)
{

    if (node == null)
        return;

    flattenTree(node.left, list);
    list.add(node.val);
    flattenTree(node.right, list);

}    

public static void main(String[] args) {

    BST bst = new BST();

    bst.add(5);
    bst.add(1);
    bst.add(0);
    bst.add(3);

    System.out.println(bst.flattenTree());

}

}

• 使用类变量:

import java.util.*;

public class BST {

private Node root;

ArrayList<Integer> list = new ArrayList<>();    

private class Node {
    private int val;             // associated data
    private Node left, right;  // left and right subtree

    public Node(int val) {
        this.val = val;

    }
}   

public ArrayList<Integer> flattenTree(){

    flattenTree(root);

    return list;
}

public void flattenTree(Node node)
{

    if (node == null)
        return;

    flattenTree(node.left);
    list.add(node.val);
    flattenTree(node.right);

}    

public static void main(String[] args) {

    BST bst = new BST();

    bst.add(5);
    bst.add(3);
    bst.add(1);
    bst.add(0);
    bst.add(3);
    bst.add(3);

    bst.printInorder();
    System.out.println(bst.flattenTree());

}

在这两种情况下我得到:

sgupta$ java BST
[0, 1, 3, 5]

我是 Java 的初学者(高中)，想知道每种方法的优缺点。

我唯一能想到的是方法 #2 不必四处传递列表，因此代码不那么困惑。

Answer 1

为了补充@caskey 的观点，我想指出第一版代码的另外两个主要优点。

首先，接受显式列表的代码更难被错误使用。如果调用第二版代码，则需要

• 确保没有其他人在并行线程中调用该方法，
• 确保列表变量已经初始化，
• 确保列表中不包含任何其他内容，并且
• 记得读完 list 后。

如果您忘记执行其中任何一项，您的程序将不会按预期运行，但您不会收到任何编译器错误来指示这一点。这使代码更难正确使用，并增加了程序中出现更多错误的可能性。

其次，第一个版本的描述更简单。代码的第一个版本可以描述为“用树的中序遍历填充给定列表”。第二个版本是“在列表 list 的现有内容后附加树的中序遍历”。很难描述第二个的作用，因此文档的负担更大。此外，第一次阅读代码的程序员更难理解它的作用。

希望这对您有所帮助!