数据结构与算法-递归与非递归方式实现先序-中序-后序遍历二叉树【八】

拼搏现实的明天。 2023-03-14 10:42 27阅读 0赞

标签（空格分隔）： 先序遍历 后序遍历 中序遍历 深度优先遍历 递归 非递归

--------------------

[上一篇文章][Link 1]已经说过了，遍历树(二叉树是树的一种特殊情况)有`深度优先遍历`和`广度优先遍历`。

> ### 深度优先遍历 ###

深度优先遍历 根据访问每个根节点与 左子树/右子树的顺序 分为 先序，中序，后序。

深度优先遍历有递归和非递归的形式。

假定二叉树的节点定义长这样：

/** * Definition for a binary tree node.*/
     function TreeNode(val) { 
          this.val = val;
          this.left = this.right = null;
     }

--------------------

## 深度优先遍历-----递归 ##

先序遍历：

var preorderTraversal = (root) => { 
        let res = []
        var helpFunc = (node) => { 
            if (node) { 
                res.push(node.val)
                helpFunc(node.left)
                helpFunc(node.right)
            }
        }
        helpFunc(root)
        // 这里也可以在helpFunc返回res，也可以将res作为一个参数传递进去，最后直接返回res。
        return res
     }

中序遍历：

var inorderTraversal = (root) => { 
        let res = []
        var helpFunc = (node) => { 
            if (node) { 
                helpFunc(node.left)
                res.push(node.val)
                helpFunc(node.right)
            }
        }
        helpFunc(root)
        // 这里也可以在helpFunc返回res，也可以将res作为一个参数传递进去，最后直接返回res。
        return res
     }

后序遍历：

var postorderTraversal = (root) => { 
        let res = []
        var helpFunc = (node) => { 
            if (node) { 
                helpFunc(node.left)
                helpFunc(node.right)
                res.push(node.val)
            }
        }
        helpFunc(root)
        // 这里也可以在helpFunc返回res，也可以将res作为一个参数传递进去，最后直接返回res。
        return res
     }

--------------------

## 深度优先遍历-----非递归 ##

先序遍历的非递归方式

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

后序遍历的非递归方式-01

var postorderTraversal = (root) => { 
        if (root === null) return []
        var result = []
        var stack = []
        stack.push(root)
        while (stack.length !==0) { 
            let node= stack.pop()
            result.unshift(node.val)  // 也可以push ，然后在最后reverse 见下方
            if (node.left) stack.push(node.left)
            if (node.right) stack.push(node.right)
            
        }
        return result
    }

后序遍历的非递归方式 -02

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

中序遍历的非递归方式

[点击这个连接][Link 2]

深度优先遍历 非递归 都是用到了栈 stack 【先进后出】  
广度优先遍历 非递归 用到了queue 【先进先出】

leetcode的 94，114，145 这 3 个题 分别是二叉树的中序 / 先序 / 后序遍历的题目。

[Link 1]: https://blog.csdn.net/a5534789/article/details/105617105
[Link 2]: https://blog.csdn.net/a5534789/article/details/100182954