概念

链式存储

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 非递归解法

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

4. 层序遍历

levelOrder(root) {
        let nodequeue = []
        let res = []
        if (root === null) {
            return []
        }
        nodequeue.push(root)
        let level = 0
        while (nodequeue.length > 0) {
            res[level] = []
            let len = nodequeue.length
            for (let i = 0; i < len; i++) {
                let node = nodequeue.shift()
                res[level].push(node.val)
                if (node.left) {
                    nodequeue.push(node.left)
                }
                if (node.right) {
                    nodequeue.push(node.right)
                }
            }
            level++
        }
    }

5. 路径查找

binaryTreePaths(root) {
        let nodestack = []
        let res = []
        let pathstack = []
        if (root === null) {
            return res
        }
        nodestack.push(root)
        pathstack.push(root.val.toString())
        while (nodestack.length > 0) {
            let node = nodestack.pop()
            let path = pathstack.pop()
            if (node.left === null && node.right === null) {
                res.unshift(path)
            }
            if (node.left) {
                nodestack.push(node.left)
                pathstack.push(path + '->' + node.left.val)
            }
            if (node.right) {
                nodestack.push(node.right)
                pathstack.push(path + '->' + node.right.val)
            }
        }
        return res
    }

线性存储