144/94/145. 二叉树的前/中/后序遍历

[luryZhu]

144 二叉树的前序遍历
94 二叉树的中序遍历
145 二叉树的后序遍历
给你二叉树的根节点 root ，返回它节点值的 前、中/后序 遍历

思路3要理解！

思路1：DFS递归

很简单

代码

前序

var preorderTraversal = function(root) {
    let ret=[];
    let dfs=function(root){
        if (!root) return
        //以下部分改变顺序
        ret.push(root.val)
        dfs(root.left)
        dfs(root.right)
    }
    dfs(root)
    return ret
};

中序

        dfs(root.left)
        ret.push(root.val)
        dfs(root.right)

后序

        dfs(root.left)
        dfs(root.right)
        ret.push(root.val)

思路2 操作入栈，普适于前、中、后序遍历

参考 sl1673495/leetcode-javascript#50

把遍历可以分成三种操作：

• 找左孩子
• 找右孩子
• 将值加入解集

前序遍历的顺序：把三种操作入栈

• 右孩子入栈
• 左孩子入栈
• 将值加入解集

建立数据结构 {type,node} 来表示操作

• type ：表示操作类型，n(getNode )or v(getVal)
• node ：表示存储的结点
  相应地，其他顺序的遍历只要改变n和v操作入栈的顺序就行

代码

前序

var preorderTraversal = function(root) {
    if (!root) return []
    let ret=[]
    let stack=[{
        type:`n`,
        node:root
    }];
    while (stack.length){
        let {type,node}=stack.pop()
        if (type==='n'){ //改变这部分顺序可以实现前/中/后序遍历
            if(node.right) stack.push({type:'n',node:node.right}) //右孩子入栈
            if(node.left) stack.push({type:'n',node:node.left}) //左孩子入栈
            stack.push({type:'v',node:node}) //值加入解集
        }
        if (type==='v'){
            ret.push(node.val)
        }
    }
    return ret
};

中序
操作：左 中 右
入栈：右 中 左

        if (type==='n'){ //改变这部分顺序可以实现前/中/后序遍历
            if(node.right) stack.push({type:'n',node:node.right}) //右孩子入栈
            stack.push({type:'v',node:node}) //值加入解集
            if(node.left) stack.push({type:'n',node:node.left}) //左孩子入栈
        }

后序
操作：左 右 中
入栈：中 右 左

        if (type==='n'){ //改变这部分顺序可以实现前/中/后序遍历
            stack.push({type:'v',node:node}) //值加入解集
            if(node.right) stack.push({type:'n',node:node.right}) //右孩子入栈
            if(node.left) stack.push({type:'n',node:node.left}) //左孩子入栈
        }

[luryZhu]

思路3：栈 重要！！

前=后，重点理解中

前序

中 左 右
先找中

• 取栈顶元素为当前结点
  • 当前结点值加入解集
  • 右孩子入栈（如果有）
  • 左孩子入栈（如果有）

代码

var preorderTraversal = function(root) {
    if (!root) return []
    let ret=[]
    let stack=[root]
    while (stack.length){
        root=stack.pop()
        ret.push(root.val)
        if(root.right)stack.push(root.right)
        if(root.left)stack.push(root.left)
    }
    return ret
};

中序

用一个栈 stack 和一个当前结点 root 来遍历：

• stack ：保存根结点
• root ：存储当前结点
  遍历顺序：左 中 右
  先找最左的结点，回退到中，再右
• 如果当前是结点
  • 当前结点入栈，取左孩子为下一个结点
• 如果当前不是结点
  • 取栈顶元素为当前结点
  • 当前结点值加入解集
  • 右孩子入栈

代码

var inorderTraversal = function(root) {
    let ret=[]
    let stack=[]
    while(root||stack.length){
        if (root){
            stack.push(root)
            root=root.left
        } else {
            root=stack.pop()
            ret.push(root.val)
            root=root.right
        }
    }
    return ret  
};

后序

先序：中 左 右
后序：左 右 中
可以直接用先序的方法做成 中 右 左，再反转结果成 左 右 中

代码

var postorderTraversal = function(root) {
    if (!root) return []
    let ret=[]
    let stack=[root]
    while (stack.length){
        root=stack.pop()
        ret.push(root.val)
        if(root.left)stack.push(root.left)  //注意这里顺序和前序相反
        if(root.right)stack.push(root.right)
    }
    return ret.reverse()
};