关于二叉树的定义，以及什么是二叉树的三种遍历（先序遍历，中序遍历，后序遍历），不是本文关注的重点，请自行查阅相关资料。本文的重点是
如何用递归和迭代分别实现二叉树的三种遍历。leetcode上有三道题分别求三种遍历结果：Binary Tree Preorder Traversal 、Binary Tree Inorder Traversal 、 Binary Tree Postorder Traversal
递归
递归解法不用多说，只需在递归部分的不同位置将节点value置入数组即可：
/** * Definition for a binary tree node. * function TreeNode（val） { * this.val = val; * this.left = this.right = null; * } *//** * @param {TreeNode} root * @return {number[]} */function dfs（root, ans） {if （！root） return;// 先序// ans.push（root.val）;dfs（root.left, ans）;// 中序// ans.push（root.val）;dfs（root.right, ans）;// 后序// ans.push（root.val）;}var preorderTraversal = function（root） {var ans = [];dfs（root, ans）;return ans;};迭代
难点是迭代。如果把二叉树看做图，那么二叉树的遍历其实就是图的深度优先遍历，而图的深度优先遍历能用手动模拟栈来解，那么二叉树的遍历也是可以的。
用栈模拟图的深度优先遍历，每次把父亲节点的儿子节点的一个入栈，并删除该儿子节点当父亲节点的所有儿子节点都被删除时，父亲节点出栈
我们以下面一棵二叉树举例：
1/ 25/ 3 4如何用栈模拟遍历该二叉树？我们用
stack 数组模拟栈。
- 将root入栈。此时
stack = [1] - 遍历root的子节点，将左子节点入栈。
stack = [1, 2] - 此时栈顶元素为
2，开始遍历它的子节点。左子节点为 3, 入栈。 stack = [1, 2, 3] - 此时栈顶元素为
3 ，它没有子节点，将它出栈。 stack = [1, 2] - 此时栈顶元素为
2，遍历它的子节点。左子节点已经被遍历，于是右子节点，入栈。 stack = [1, 2, 4] - 此时栈顶元素为
4，和 3 一样它也没有左右子节点，出栈。stack = [1, 2] - 此时栈顶元素为
2 , 当父亲节点的所有儿子节点都被删除时，父亲节点出栈，于是它出栈。 stack = [1] - 此时栈顶元素为
1，它的左子节点已经遍历，遍历右子节点，将 5 入栈。 stack = [1, 5] - 此时栈顶元素为
5, 它没有子节点，出栈。 stack = [1] - 此时栈顶元素为
1, 它的子节点都被遍历过了，出栈。 stack=[] - 此时stack数组长度为0，迭代结束。
先序遍历只需按照如上的步骤模拟栈，在每次入栈的时候将节点的value值放入ans数组即可。
/** * Definition for a binary tree node. * function TreeNode（val） { * this.val = val; * this.left = this.right = null; * } *//** * @param {TreeNode} root * @return {number[]} */var preorderTraversal = function（root） {if （！root） return [];var stack = []// 栈模拟, ans = [];stack.push（root）;ans.push（root.val）;while （stack.length） {var elem = stack[stack.length - 1];if （elem.left） {ans.push（elem.left.val）;stack.push（elem.left）;elem.left = null;} else if （elem.right） {ans.push（elem.right.val）;stack.push（elem.right）;elem.right = null;} elsestack.pop（）;}return ans;};还有一种更简洁的代码写法，因为二叉树父节点最多就两个子节点，所以直接遍历两个节点，然后在栈中删除父节点即可。
/** * Definition for a binary tree node. * function TreeNode（val） { * this.val = val; * this.left = this.right = null; * } *//** * @param {TreeNode} root * @return {number[]} */var preorderTraversal = function（root） {if （！root） return [];var stack = []// 栈模拟, ans = [];stack.push（root）;while （stack.length） {var elem = stack.pop（）;ans.push（elem.val）;if （elem.right）stack.push（elem.right）;if （elem.left）stack.push（elem.left）;}return ans;};和先序遍历略有不同的是，先序遍历是先遍历父节点，所以父节点的value值要在入栈的时候就放入ans数组，而后序遍历是最后遍历父节点，所以当父节点出栈时（此时左右子树都已经遍历完毕），把节点的value值放入ans数组即可：
var postorderTraversal = function（root） {if （！root） return [];var stack = []// 栈模拟, ans = [];stack.push（root）;while （stack.length） {var elem = stack[stack.length - 1];if （elem.left） {stack.push（elem.left）;elem.left = null;} else if （elem.right） {stack.push（elem.right）;elem.right = null;} else {var a = stack.pop（）;ans.push（a.val）;}}return ans;};中序遍历是三大遍历里最复杂的。先序遍历是先遍历父节点，所以节点入栈时存储value值，后序遍历是最后遍历父节点，所以节点出栈时存储value值，中序遍历呢？在leetcode中，中序遍历这题比先序和后序多了一个tag -
hash table，而如何hash也正是本题难点。中序遍历是在父节点的左子树遍历完后，将父节点的value值存入ans数组的，那么如何判断左子树已经遍历完了呢？比如下面这棵二叉树：
1/ 25/ 3 4当遍历到
2 这个节点时，它有左节点，按照先序和后序遍历的做法，将左节点入栈，同时将
2 所在节点的left置为null，当节点
3 出栈后，判断
2 节点的左右子节点，这时发现左节点为null,说明已经遍历过了，于是
value=2 存入ans数组，然后
4 所在节点入栈，然后
4 再出栈，
这时栈顶元素又是2，而这时再次判断左右子节点，发现左子节点为null，认为左子节点遍历过了，value=2再次存入ans数组！看到这里，你或许有点眉目了，
我们不能用置为null来表示节点已经遍历，而应该用正确的hash方式，这里我用
elem.left=1 表示elem的左节点已经被遍历过了，用
elem.left=0 表示elem节点所在的值已经存入ans数组了。
var inorderTraversal = function（root） {if （！root） return [];var stack = [], ans = [];stack.push（root）;while （stack.length） {var elem = stack[stack.length - 1];if （elem.left === 1） {elem.left = 0;ans.push（elem.val）;} else if （elem.left） {stack.push（elem.left）;elem.left = 1;} else if （elem.left === null） {elem.left = 1;} else if （elem.right） {stack.push（elem.right）;elem.right = null;} else {stack.pop（）;}}return ans;};二叉树的常见问题及其解决程序 http://www.linuxidc.com/Linux/2013-04/83661.htm【递归】二叉树的先序建立及遍历 http://www.linuxidc.com/Linux/2012-12/75608.htm在JAVA中实现的二叉树结构 http://www.linuxidc.com/Linux/2008-12/17690.htm【非递归】二叉树的建立及遍历 http://www.linuxidc.com/Linux/2012-12/75607.htm二叉树递归实现与二重指针 http://www.linuxidc.com/Linux/2013-07/87373.htm二叉树先序中序非递归算法 http://www.linuxidc.com/Linux/2014-06/102935.htm
轻松搞定面试中的二叉树题目 http://www.linuxidc.com/linux/2014-07/104857.htm
本文永久更新链接地址：http://www.linuxidc.com/Linux/2015-09/123493.htm
易网时代-编程资源站