二叉树的遍历

前序遍历 - 中序遍历 - 后序遍历

前序遍历

leetcode-144题 - 中左右

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { *     this.val = (val===undefined ? 0 : val) *     this.left = (left===undefined ? null : left) *     this.right = (right===undefined ? null : right) * } */

前序遍历 - 递归

• 思路
  • 定义一个存放结果的数组 res
  • 定义一个递归的方法 order
  • 传入中间节点，判断是否有👈节点，如果有则递归左节点，（此时左节点作为中间节点进入order方法），右节点同上。

var preorderTraversal = function(root) {    const res = []    if(root === null){        return res    }    const order = (node) => {        res.push(node.val)        if(node.left !== null){            order(node.left)        }        if(node.right !== null){            order(node.right)        }    }    order(root)    return res};

前序遍历 - 迭代

• 思路
  • 定义一个存放结果的数组 res
  • 定义一个栈（数组） stack
  • 将中间节点传入栈中
  • while栈不为空，将栈中的节点取出（取出节点时，将该节点传入res）
  • 利用栈先进后出规则，先入栈👉节点，后入栈👈节点，
  • 从栈顶取出一个节点，将该节点的右左节点入栈

var preorderTraversal = function(root) {    const res = []    if(root === null){        return res    }    const stack = []    stack.push(root)    while(stack.length > 0){        const current = stack.pop()        res.push(current.val)        if(current.right !== null){            stack.push(current.right)        }        if(current.left !== null){            stack.push(current.left)        }    }    return res};

中序遍历

leetcode-94题 - 左中右

中序遍历 - 递归

• 思路
  • 先遍历左子树，然后访问根结点，最后遍历右子树。

var inorderTraversal = function(root) {    const res = []    if(root === null){        return res    }    const order = (node) => {        if(node.left !== null){            order(node.left)        }        res.push(node.val)        if(node.right !== null){            order(node.right)        }    }    order(root)    return res};

中序遍历 - 迭代

• 思路
  • 先遍历左子树，依次入栈
  • while栈不为空，执行出栈
  • 出栈时判断current节点是否有右节点，有右节点则遍历右节点的左子树，依次进栈

var inorderTraversal = function(root) {    const res = [];    if(root === null) {        return res;    }    const stack = [];    // 开始，将左侧节点传入栈中    let temp = root;    while(temp !== null){        stack.push(temp)        temp = temp.left;    }
    while(stack.length > 0){        // 出栈        const current = stack.pop()        res.push(current.val)        // 如果有右侧节点，将 右侧节点 的 左侧子节点 传入栈中        if(current.right !== null) {            let temp2 = current.right            while(temp2 !== null) {                stack.push(temp2)                temp2 = temp2.left            }        }    }    return res};

后序遍历

leetcode-145题 - 左右中

后序遍历 - 递归

• 思路
  • 先遍历左子树，然后遍历右子树，最后访问根结点。

var postorderTraversal = function(root) {    const res = [];    if(root === null){        return res    }
    const order = (node) => {        if(node.left !== null){            order(node.left)        }        if(node.right !== null){            order(node.right)        }        res.push(node.val)    }    order(root)    return res;};

后序遍历 - 迭代

• 思路
  • 先遍历左子树，依次入栈
  • while栈不为空，执行出栈