力扣二叉树的三种遍历

这篇文章类比三种遍历的写法，每个遍历利用两种方法，分别是递归和迭代，帮助更好的学习二叉树的相关知识。

一、前序

两种方法：

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) { const res = []; const preorder = (node) => { if(node === null) return; //先搜集根节点 res.push(node.val); //递归遍历左子树 preorder(node.left); //递归遍历右子树 preorder(node.right) } preorder(root); return res; };

2.迭代

/** * 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) { const res = []; // 存储遍历结果 const stk = []; // 模拟递归的栈 // 循环条件和中序/后序一致：当前节点非空 或 栈非空 while (root || stk.length) { while (root) { res.push(root.val); stk.push(root); root = root.left; } root = stk.pop(); root = root.right; } return res; };

二、中序

两种方法：

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 inorderTraversal = function(root) { const res = []; const inorder = (node) => { if (node === null) return; // 先递归遍历左子树 inorder(node.left); // 收集当前节点值 res.push(node.val); // 再递归遍历右子树 inorder(node.right); }; inorder(root); return res; };

2.迭代

var inorderTraversal = function(root) { const res = []; const stk = []; while (root || stk.length) { while (root) { stk.push(root); root = root.left; } root = stk.pop(); res.push(root.val); root = root.right; } return res; };

三、后序

两种方法：

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 postorderTraversal = function(root) { const res = []; const postorder = (node) => { if(node === null) return; //递归遍历左子树 postorder(node.left); //递归遍历右子树 postorder(node.right); //先搜集根节点 res.push(node.val); } postorder(root); return res; };

2.迭代

var postorderTraversal = function(root) { const res = []; const stk = []; let prev = null; while (root || stk.length) { while (root) { stk.push(root); root = root.left; } root = stk.pop(); if (!root.right || root.right === prev) { res.push(root.val); prev = root; root = null; } else { stk.push(root); root = root.right; } } return res; };