问答

当前位置
  • 首页
  • 问答
  • 95.Validate Binary Search Tree 先序遍历动态数组解法

95.Validate Binary Search Tree 先序遍历动态数组解法

  • Ta: Stella助教

我用除了分治的另外一种方法来写了这道题的答案,利用了BST的第一个性质:中序遍历递增。首先存储输入BST的中序遍历数组,然后再遍历一下这些数字看看是否为直升序(无重复)。(老师用的分治解法利用的是BST第二个性质:即左子树最大值<当前值<右子树最小值,且左右子树也是BST)

我的问题是,一般来说,一个变量开为局部变量或者全局变量,如果在程序都可运行的情况下,是不是没有区别的,比如这个arr数组?

局部变量写法:
```
public boolean isValidBST(TreeNode root) {
//inorder traversal
List arr = new ArrayList<>();
traverse(root, arr);

    //check arr for ascending order
    if (arr.size() > 1) {
        for (int i = 1; i < arr.size(); i++) {
            if (arr.get(i) <= arr.get(i - 1)) {
                return false;
            }
        }
    }

    return true;
}

private void traverse(TreeNode root, List<Integer> arr) {
    if (root == null) {
        return;
    }
    traverse(root.left, arr);
    arr.add(root.val);
    traverse(root.right, arr);
}
    ```

    全局变量写法:
    ```
    List<Integer> arr = new ArrayList<>();
public boolean isValidBST(TreeNode root) {
    //inorder traversal
    traverse(root);

    //check arr for ascending order
    if (arr.size() > 1) {
        for (int i = 1; i < arr.size(); i++) {
            if (arr.get(i) <= arr.get(i - 1)) {
                return false;
            }
        }
    }

    return true;
}

private void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    traverse(root.left);
    arr.add(root.val);
    traverse(root.right);
}
    ```

1 个回复

2019-09-11 carry

全局变量保存在内存的全局存储区中,占用静态的存储单元;局部变量保存在栈中,只有在所在函数被调用时才动态地为变量分配存储单元。
在算法题中,全局变量可以减少传参等操作,可能更加方便,解题中两者并无太大区别。开发中,全局变量的使用,可能会增加不同的模块之间的耦合度,过多地使用全局变量会增加维护的难度。

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1