概念

链式存储

1. 先序遍历

2.1 递归解法

解题思路
代码

preorder_recur(node) {
        if (!node) {
            node = this.root
        }
        console.log(node.data)
        this.preorder_recur(node.left)
        this.preorder_recur(node.right)
    }

1.2 非递归解法

解题思路
代码

preorder(node) {
        if (!node) {
            node = this.root
        }
        let stack = []
        let res = []
        stack.push(node)
        if (node === null) {
            return []
        }
        while (stack.length > 0) {
            let node = stack.pop()
            res.push(node.val)
            if (node.right) {
                stack.push(node.right)
            }
            if (node.left) {
                stack.push(node.left)
            }
        }
        return res
    }

2. 中序遍历

2.1 递归解法

if (!node) {
            node = this.root
        }
        this.preorder_recur(node.left)
        console.log(node.data)
        this.preorder_recur(node.right)

2.2 非递归解法

inorder(node) {
        if (!node) {
            node = this.root
        }
        let stack = []
        let res = []
        if (node === null) {
            return []
        }
        while (node !== null || stack.length > 0) {
            while (node !== null) {
                stack.push(node)
                node = node.left
            }
            node = stack.pop()
            res.push(node.data)
            node = node.right
        }
    }

3. 后序遍历

3.1 递归解法

postorder_recur(node) {
        if (!node) {
            node = this.root
        }
        this.preorder_recur(node.left)
        this.preorder_recur(node.right)
        console.log(node.data)
    }

3.2 非递归解法

线性存储