编辑代码

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])

//递归
function inorderTraversal(tree) {
    let res = []
    const inorder = (tree) => {
        if (tree == null) return
        inorder(tree.left)
        res.push(tree.val)
        inorder(tree.right)
    }
    inorder(tree);
    return res
}
const traversalRes = inorderTraversal(tree1)
// console.log(traversalRes)

// 迭代1
function recursionTraversal(tree) {
    let res = []
    let stack = []
    const inorder = (tree) => {
        if (tree != null) {
            stack.push(tree)
            inorder(tree.left)
        }
        if (stack.length == 0) return
        tree = stack.pop()
        res.push(tree.val)
        inorder(tree.right)
    }
    inorder(tree)
    return res
}

const traversalRes1 = recursionTraversal(tree1)
// console.log(traversalRes1)
// 迭代2
function recursionTraversal2(tree) {
    let res = []
    let stack = []
    while (tree || stack.length > 0) {
        while (tree) {
            stack.push(tree)
            tree = tree.left
        }
        tree = stack.pop()
        res.push(tree.val)
        tree = tree.right
    }
    return res
}

const traversalRes2 = recursionTraversal2(tree1)
console.log(traversalRes2)