递归版

先序遍历算法口诀

• 访问根节点
• 对左子树进行先序遍历
• 对右子树进行先序遍历

const preorder = (root) => {
      if(!root) { return }
      console.log(root.val)
      preorder(root.left)
      preorder(root.right)
}

中序遍历算法口诀

•  对根节点的左子树进行中序遍历
• 访问根节点
• 对跟几点的右子树进行中序遍历

const inorder = (root) =>{
    if(!root) {return}
    inorder(roor.left)
    console.log(root.val)
    inorder(roor.right)

}

后序遍历算法口诀

• 对根节点的左子树进行后序遍历
• 对根节点的右子树进行后序遍历
• 访问根节点

const postorder = ( root ) => {
   if(!root) { return}
   postorder（root.left）
   postorder（root.right）
   console.log(root.val)
} 

 

非递归版

 

先序遍历算法

• 访问根节点
• 对左子树进行先序遍历
• 对右子树进行先序遍历

const preorder = (root) => {
     if(!root){ return}
     const stack = [root]// 栈
     while(stack.length){ 
        const n = stack.pop() // 出栈
        console.log(n)
        //  后进先出特性 所以先right 先入栈
        if(stack.right) stack.push（stack.right）
        if(stack.left) stack.push（stack.left）
     }
}

中序遍历

•  对根节点的左子树进行中序遍历
• 访问根节点
• 对跟几点的右子树进行中序遍历、

const inorder = (root) => {
      if(!root) { return}
      const stack = [] ;
      let p  = root ;  // 声明一个指针
      while(stack.length || p){ // stack 有值 或者 p 不为空 一直循环
         while(p){
            stack.push(p) // 入栈
            p = p.left ; // 指针指向左节点
         }
         const n = stack.pop() // 出栈
         console.log(n.val) // 访问根节点
         p = n.right // 指针指向右节点
      }
}

后序遍历算法口诀

• 对根节点的左子树进行后序遍历
• 对根节点的右子树进行后序遍历
• 访问根节点

const postorder = ( root ) {
    if(!root) { rturn}
     const stack = [root] // 栈 
     const outputStack = [] // outputStack 栈  存储stack栈的反序
    while(stack.length) {
       const n  = stack.pop();  // 出栈 
       outputStack.push(n)  // 存档到outputStack栈中
       if(n.left) stack.push(n.left)
       if(n.left) stack.push(n.right)
    }
    while(outputStack.length){
         const n = outputStack.pop() // 从 outputStack  出栈
        console.log(n.val) // 访问节点
    }
}