LeetCode 栈、队列、优先队列专题 2：二叉树的三种非递归
LeetCode 栈、队列、优先队列专题 2：二叉树的三种非递归实现
对于递归而言，简单来说就是自己调用自己，但是再一次调用自己，又有不一样的地方，具体表现就是参数不同。
通常我们写递归程序的时候，是不会直接使用栈的。因为操作系统在执行递归程序的时候，就帮助我们使用了栈。我们可以把操作系统为了帮助我们执行递归程序而使用的栈，称作“系统栈”。
从操作系统的角度来看，实现递归的手段，恰恰是使用了栈。对于栈的熟练掌握，可以加深我们对递归问题的理解。
之后的若干章节，我们还会多次使用递归。
递归在算法的学习中是举足轻重的。所以，我们十分有必要学习好栈这种数据结构。
对于递归的学习，我们使用"二叉树"作为入手点。以二叉树中的算法来理解递归。因为二叉树的定义就是通过递归定义的。
二叉树的遍历有三种遍历：1、前序遍历；2、中序遍历；3、后序遍历。分别就对应了 LeetCode 第 144 题、第 94 题、第 145 题。
关于二叉树的遍历分为以下四种：先序遍历、中序遍历、后序遍历、层序遍历。其中先序、中序、后序遍历又分别有递归方式和非递归方式。
例题：LeetCode 上第 144 题：二叉树的前序遍历
传送门：英文网址：144. Binary Tree Preorder Traversal ，中文网址：144. 二叉树的前序遍历 。
给定一个二叉树，返回它的 前序 遍历。
示例:
输入: [1,null,2,3] 1 \ 2 / 3 输出: [1,2,3]进阶: 递归算法很简单，你可以通过迭代算法完成吗？
递归的写法。下面这种写法是错的：这是我想当然，轻视问题而写出的错误程序。
/**
* 使用递归的方式实现二叉树的前序遍历
*
* @param root
* @return
*/
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root != null) {
result.add(root.val);
preorderTraversal(root.left);
preorderTraversal(root.right);
}
return result;
}
因为这里要求返回一个数组，而不是在遍历的时候打印这个节点的值，所以如果要使用递归来解决问题，应该在这个方法之外声明一个成员变量，作为返回值；并且另外声明一个递归函数来完成递归的任务，正确的代码如下：
Java 代码：
public class Solution3 {
private List<Integer> result = new ArrayList<>();
/**
* 使用递归的方式实现二叉树的前序遍历
*
* @param root
* @return
*/
public List<Integer> preorderTraversal(TreeNode root) {
preorder(root);
return result;
}
private void preorder(TreeNode root) {
if (root != null) {
result.add(root.val);
preorderTraversal(root.left);
preorderTraversal(root.right);
}
}
}
Python 代码：在入栈的时候，就可以判断是不是空，只将非空结点入栈。顺序问题：如果我们期望代码执行的顺序是 1 2 3 ， 那么，我们应该以 3 2 1 的方式将代码入栈。即顺序执行 a b c 这件事情，须要往栈里依次推入 c b a
# 掌握前序遍历，使用栈的写法
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
# 教科书上的前序遍历非递归写法
class Solution:
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root:
return []
stack = [root]
res = []
while stack:
node = stack.pop()
# 前序遍历：先自己，再左孩子，右孩子
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
res.append(node.val)
return res
我们借助“栈”完成了二叉树的非递归前序遍历，其实借助这种思路，即“模拟系统栈”，可以完成二叉树的 3 种遍历。
Python 代码2：“模拟系统栈”实现二叉树的“前序遍历”。
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def preorderTraversal(self, root):
if not root:
return []
res = []
stack = [(1, root)]
while stack:
command, node = stack.pop()
if command == 0:
res.append(node.val)
else:
if node.right:
stack.append((1, node.right))
if node.left:
stack.append((1, node.left))
stack.append((0, node))
return res
Java 代码：非递归的写法，使用模拟的系统栈，写出一个非递归的程序
enum UseType {
RECURSION, ADD
}
/**
* 我们自定义的 Command 类
*/
class MyCommand {
UseType useType; // 是对这个节点进行操作，还是递归调用这个节点
TreeNode treeNode;
MyCommand(UseType useType, TreeNode treeNode) {
this.useType = useType;
this.treeNode = treeNode;
}
}
public class Solution4 {
/**
* 非递归就是要顺序执行，所以不用自己声明一个递归函数来完成
*
* @param root
* @return
*/
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Stack<MyCommand> stack = new Stack<>();
stack.push(new MyCommand(UseType.RECURSION, root));
while (!stack.isEmpty()) {
MyCommand currentCommand = stack.pop();
if (UseType.ADD == currentCommand.useType) {
result.add(currentCommand.treeNode.val);
} else {
assert UseType.RECURSION == currentCommand.useType; // 模拟系统栈的作用，注意，应该倒过来写
if (currentCommand.treeNode.right != null) {
stack.push(new MyCommand(UseType.RECURSION, currentCommand.treeNode.right));
}
if (currentCommand.treeNode.left != null) {
stack.push(new MyCommand(UseType.RECURSION, currentCommand.treeNode.left));
}
stack.push(new MyCommand(UseType.ADD, currentCommand.treeNode));
}
}
return result;
}
}
LeetCode 第 94 题：94. 二叉树的中序遍历
传送门：英文网址：94. Binary Tree Inorder Traversal ，中文网址：94. 二叉树的中序遍历 。
给定一个二叉树，返回它的中序 遍历。
示例:
输入: [1,null,2,3] 1 \ 2 / 3 输出: [1,3,2]进阶: 递归算法很简单，你可以通过迭代算法完成吗？
Python 代码：
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def inorderTraversal(self, root):
if not root:
return []
stack = [(1, root)]
res = []
while stack:
command, node = stack.pop()
if command == 0:
res.append(node.val)
else:
if node.right:
stack.append((1, node.right))
stack.append((0, node))
if node.left:
stack.append((1, node.left))
return res
LeetCode 第 145 题：二叉树的后序遍历
传送门：英文网址：145. Binary Tree Postorder Traversal ，中文网址：145. 二叉树的后序遍历 。
给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。
示例:
输入: 3 输出: [ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3], [1,null,2,null,3] ] 解释: 以上的输出对应以下 5 种不同结构的二叉搜索树： 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3
Python 代码：
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def postorderTraversal(self, root):
if not root:
return []
stack = [(1, root)]
res = []
while stack:
command, node = stack.pop()
if command == 0:
res.append(node.val)
else:
# 后序遍历：先左右子树，再自己
# 入栈顺序：自己、右子树、左子树
stack.append((0, node))
if node.right:
stack.append((1, node.right))
if node.left:
stack.append((1, node.left))
return res
上面的过程更好地体现了递归过程中系统栈的作用，按照这种方式，所有的递归的代码都可以改造成非递归的代码。
（本节完）
