<< 返回算法列表

实现二叉树先序，中序和后序遍历

描述 分别按照二叉树先序，中序和后序打印所有的节点。

示例1

输入：
{1,2,3}

返回值：
[[1,2,3],[2,1,3],[2,3,1]]

解答

注意：先中后指的是跟的次序

1. 先(根)序遍历（根左右）
2. 中(根)序遍历（左根右）
3. 后(根)序遍历（左右根）

 function TreeNode(x) {
    this.val = x
    this.left = null
    this.right = null
 }
 
 
function threeOrders( root ) {
    // write code here
    let preArr = []
    let midArr = []
    let postArr = []
    preOrder2(root)
    midOrder(root)
    postOrder(root)
    function preOrder(root) {
        if(!root) return
        preArr.push(root.val)
        preOrder(root.left)
 
        preOrder(root.right)
    }
 
    //也可不使用递归
    function preOrder2(root) {
        if(!root) return
        let stack = []
        let p = root
        stack.push(p)
        while(stack.length > 0) {
          p = stack.pop()
          preArr.push(p.val)
          if(p.right) stack.push(p.right)
          if(p.left) stack.push(p.left)
        }
    }
 
    function midOrder(root) {
        if(!root) return
 
        midOrder(root.left)
        midArr.push(root.val)
        midOrder(root.right)        
    }
 
    function postOrder(root) {
        if(!root) return
        postOrder(root.left)
        postOrder(root.right)  
        postArr.push(root.val)
 
    }
    return [preArr, midArr, postArr]
}