后序遍历

算法

递归

const postOrderTraversal = (root) => {
	if (!root) return [];
	const res = [];
	const postOrderRecursion = (node) => {
		if (node.left) postOrderRecursion(node.left);
		if (node.right) postOrderRecursion(node.right);
		res.push(node.val);
	};
	postOrderRecursion(root);
	return res;
};

迭代一

我们使用变量temp来指向栈顶的元素

• 如果栈顶元素temp有左孩子left且他的左孩子、右孩子都不等于root，那么我们将他的左孩子推入栈stack
• 如果栈顶元素temp不满足之前的判断，且temp有右孩子，且它的右孩子不等于root，那么我们将它的右孩子推入栈stack
• 如果之前的都不满足，那我们将栈顶元素推出栈，将出栈结点的值压入结果数组并且让root等于这个出栈节点

在第一步中判断左、右孩子是否不等于root，是因为root保存了之前的出栈节点的信息（即他的左、右孩子），因为这个元素已经操作过了，所以我们避免重复操作要判断左孩子不等于root；在第二步中判断右孩子不等于root同理

但是要注意第二步中不能判断temp.left !== root，因为当左孩子没有左子树回溯到当前节点时，此时root保存的是左孩子，我们此时需要推入右孩子，但是这个时候temp.left恰好就是root，所以不能判断；当然也不用判断，当右孩子操作完回溯到当前节点时，root已经更新为了右孩子，我们只判断temp.right !== root就已经完备了

const postOrderTraversal = (root) => {
	if (!root) return [];
	const res = [];
	const stack = [root];
	let temp = null;
	while (stack.length) {
		temp = stack[stack.length - 1];
		if (temp.left && temp.left !== root && temp.right !== root) {
			stack.push(temp.left);
		} else if (temp.right && temp.right !== root) {
			stack.push(temp.right);
		} else {
			res.push(stack.pop().val);
			root = temp;
		}
	}
	return res;
};

迭代二

因为前序遍历是按照root -> left -> right的顺序操作的，后序遍历是按照left -> right -> root的顺序操作，如果我们：

• 我们将前序遍历的结果倒序插入就会变成right -> left -> root，然后
• 我们将先序遍历先操作左子树改为先操作右子树，那么结果就会变成left -> right -> root正好是后序遍历

参考前序遍历 - 迭代二：

• 将操作推入结果数组的push()操作改成unshift()，就完成了第一条
• 然后我们每次先遍历右子树，直到没有右孩子后我们回溯到父节点，再从这个节点的左节点继续遍历右子树，就完成了第二点

const postOrderTraversal = (root) => {
	if (!root) return [];
	const res = [];
	const stack = [];
	while (root || stack.length) {
		if (root) {
			stack.push(root);
			res.unshift(root.val);
			root = root.right;
		} else {
			root = stack.pop();
			root = root.left;
		}
	}
	return res;
};