二叉树的前、中和后序遍历的递归与迭代实现

1. 前序遍历

1.1 递归

/*** 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)* }*/
/*** @param {TreeNode} root* @return {number[]}*/
var preorderTraversal = function(root) {let result = []traversal(root, result)return result
};function traversal(root, res) {if(root == null) returnres.push(root.val)traversal(root.left, res)  // 左子树traversal(root.right, res)  // 右子树
}

1.2 迭代

var preorderTraversal = function (root) {if (root == null) return []let result = []let stash = [root]while (stash.length) {const curNode = stash.pop()// 第一步的时候 先访问根节点result.push(curNode.val)// 现加入栈的是右子树然后再是左子树 这样从栈中先弹出的就是左子树 后弹出的才子右子树if (curNode.right) stash.push(curNode.right)if (curNode.left) stash.push(curNode.left)}return result
};

2. 中序遍历

2.1 递归

var inorderTraversal = function(root) {let result = []let traversal = (node, res) => {if(node == null) return// 左traversal(node.left, res)// 中res.push(node.val)// 右traversal(node.right, res)}traversal(root, result)return result
};

2.2 迭代

var inorderTraversal = function (root) {let result = []let stash = []let node = rootwhile (node || stash.length) {// 遍历左子树while (node) {stash.push(node)node = node.left}// 中node = stash.pop()result.push(node.val)// 右node = node.right}return result
};

3. 后序遍历

3.1 递归

var postorderTraversal = function(root) {let result = []let traversal = (node, res) => {if(node == null) return// 左traversal(node.left, res)// 右traversal(node.right, res)// 中res.push(node.val)}traversal(root, result)return result
};

3.2 迭代

var postorderTraversal = function (root) {if(!root) return []let result = []let stash = [root]while (stash.length) {let curNode = stash.pop()result.unshift(curNode.val)   // 核心unshiftif (curNode.left) stash.push(curNode.left)if (curNode.right) stash.push(curNode.right)}return result
};