算法通关村第七关——递归和迭代实现二叉树前中后序遍历

1.递归

1.1 熟悉递归

所有的递归有两个基本特征：

1. 执行时范围不断缩小，这样才能触底反弹。
2. 终止判断在调用递归的前面。

写递归的步骤：

1. 从小到大递推。
2. 分情况讨论，明确结束条件。
3. 组合出完整方法。
4. 想验证就从大到小画图推演。

1.2 递归实现二叉树的前中后序遍历

/*** @param {TreeNode} root* @return {number[]}*/
var preorderTraversal = function(root) {const nodeArray = [];addNode(root, nodeArray);return nodeArray;   
};function addNode(node, res) {if (!node) {return res;}// 前、中、后序遍历只需调换下面三行代码位置res.push(node.val);	// 中addNode(node.left, res); // 左addNode(node.right, res); // 右
}

2.迭代

2.1 迭代实现二叉树前中后序遍历

迭代主要是模拟一个系统栈出来，将节点压入栈中，再取出。前中序遍历容易理解，后序遍历较为复杂，涉及到反转操作。

前序遍历

 */
/*** @param {TreeNode} root* @return {number[]}*/
var preorderTraversal = function(root) {const nodeQueue = [];if (!root) {return nodeQueue;}const nodeStack = [];let treeNode = root;while (nodeStack.length !== 0 || treeNode) {while (treeNode) {nodeQueue.push(treeNode.val);nodeStack.push(treeNode);treeNode = treeNode.left;}treeNode = nodeStack.pop();treeNode = treeNode.right;}return nodeQueue;  
};

中序遍历

/*** @param {TreeNode} root* @return {number[]}*/
var inorderTraversal = function(root) {const nodeQueue = [];const nodeStack = [];if (!root) {return nodeQueue;}let treeNode = root;while (nodeStack.length !== 0 || treeNode) {		while (treeNode) {nodeStack.push(treeNode);treeNode = treeNode.left;}treeNode = nodeStack.pop()nodeQueue.push(treeNode.val);treeNode = treeNode.right;}return nodeQueue;
};

后序遍历

分析：

观察后序遍历的结果是:1, 2, 3, 8, 9, 7, 6,如果将其反转的话就是6, 7, 9, 8, 3, 2, 1

反转后的后序遍历与前序遍历相比就是左右反了。前序遍历是中左右，后序遍历是左右中，只要调整前序遍历的左右顺序就可以得到后序遍历。

function postOrderTraversal(root) {const nodeQueue = [];const nodeStack = [];if (!root) {return nodeQueue;}let treeNode = root;while (nodeStack.length !== 0 || treeNode) {while (treeNode) {nodeQueue.push(treeNode.val)nodeStack.push(treeNode);treeNode = treeNode.right;}treeNode = nodeStack.pop();treeNode = treeNode.left();}nodeQueue.reverse();   // 将其进行反转return nodeQueue;
}