JavaScript使用迭代方法中序遍历二叉树相关问题

Question

使用迭代方法解决中序遍历二叉树，下面代码中存在什么问题，不改变闭包保存结果的方式，只使用root一个参数，修改下面代码使其运行正确

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function (root) {
    let stack = [];
    let res = [];
    let cur = root;
    const inOrder = function (root) {
        while (stack.length || cur) {
            if (cur) {
                stack.push(cur.val)
                cur = cur.left
            } else {
                cur = stack.pop();
                res.push(cur.val);
                cur = cur.right;
            }
        }
    }
    inOrder(root);
    return res;
};

Answer 1

以下内容由CHATGPT及阿里嘎多学长共同生成、有用望采纳：

---

在您提供的代码中，确实存在几个问题，我将一一指出并提供修改建议：

1. 栈中存储的应该是节点而不是节点的值：在您的代码中，stack 被用来存储节点的值，但实际上应该存储节点本身，这样我们才能访问节点的右子节点。

2. inOrder 函数应该使用 root 参数而不是局部变量 cur：您的 inOrder 函数应该接受 root 作为参数，而不是依赖外部的 cur 变量。

3. inOrder 函数需要正确处理节点的遍历逻辑：代码中的逻辑需要调整以确保正确的中序遍历顺序。

下面是修改后的代码：

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function (root) {
    let stack = [];
    let res = [];
    let cur = root;

    const inOrder = function (node) {
        while (node || stack.length > 0) {
            if (node) {
                stack.push(node);
                node = node.left;
            } else {
                node = stack.pop();
                res.push(node.val);
                node = node.right;
            }
        }
    };

    inOrder(cur); // 注意这里传入的是 cur，而不是 root，因为我们需要从 cur 开始遍历
    return res;
};

请注意，这里我保留了 cur 变量，因为我们希望从 cur 开始遍历，而不是每次都从 root 开始。如果确实需要只使用 root 作为参数，我们可以在 inOrder 函数中添加一个参数来接收当前节点，但这将改变闭包保存结果的方式。

另外，我没有提供参考链接，因为这个问题主要是关于代码逻辑的修改，而不是需要参考外部资源。如果您需要进一步的解释或示例，我可以提供更多信息。