编辑代码

function BinarySearchTreeNode(list) {
    let root
    list.forEach((e) => {
        if (root == null) {
            root = new TreeNode(e);
        } else {
            instert(root, new TreeNode(e));
        }
    })

    function TreeNode(val, left, right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }


    function instert(node, newNode) {
        if (newNode.val < node.val) {
            if (node.left == null) {
                node.left = newNode;
            } else {
                instert(node.left, newNode);
            }
        } else {
            if (node.right == null) {
                node.right = newNode;
            } else {
                instert(node.right, newNode);
            }
        }
    }

    return root
}

const tree1 = BinarySearchTreeNode([5, 3, 1, 4, 8, 6, 9])

var inorderTraversal = function (root) {
    const res = [];
    let predecessor = null;

    while (root) {
        if (root.left) {
            // predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止
            predecessor = root.left;
            while (predecessor.right && predecessor.right !== root) {
                predecessor = predecessor.right;
            }

            // 让 predecessor 的右指针指向 root，继续遍历左子树
            if (!predecessor.right) {
                //标记该点访问过
                predecessor.right = root;
                root = root.left;
            }
            // 说明左子树已经访问完了，我们需要断开链接
            else {
                res.push(root.val);
                predecessor.right = null;
                root = root.right;
            }
        }
        // 如果没有左孩子，则直接访问右孩子
        else {
            res.push(root.val);
            root = root.right;
        }
    }

    return res;
};

const traversalRes = inorderTraversal(tree1)
console.log(traversalRes)