Java-二叉树后序遍历递归非递归
目录
Java 二叉树后序遍历（递归/非递归）
Java 二叉树后序遍历（递归/非递归）
简介： 遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。
设L、D、R分别表示遍历左子树、访问根结点和遍历右子树， 则对一棵二叉树的遍历有几种情况：DLR（称为先序遍历），LDR（称为中序遍历），LRD （称为后序遍历），层次遍历。
后序遍历
后序遍历：首先遍历左子树，然后遍历右子树，最后访问根结点。
如图所示二叉树的后序遍历结果为：[8,9,4,15,7,20,3]
代码实现
递归方式
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
postorder(root, res);
return res;
}
public void postorder(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
postorder(root.left, res);
postorder(root.right, res);
res.add(root.val);
}非递归方式
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if (root == null) {
return res;
}
Deque<TreeNode> stack = new LinkedList<TreeNode>();
TreeNode prev = null;
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if (root.right == null || root.right == prev) {
res.add(root.val);
prev = root;
root = null;
} else {
stack.push(root);
root = root.right;
}
}
return res;
}完整代码：
public static void main(String[] args) {
TreeNode root = new TreeNode(3);
TreeNode n1 = new TreeNode(9);
TreeNode n2 = new TreeNode(20);
TreeNode n3 = new TreeNode(8);
TreeNode n4 = new TreeNode(15);
TreeNode n5 = new TreeNode(7);
TreeNode n6 = new TreeNode(4);
root.left = n1;
root.right = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;
n4.left = n6;
List<Integer> rs = postorderTraversal(root);
System.out.println("递归中序遍历结果：" + rs);
rs = postorderTraversal02(root);
System.out.println("非递归中序遍历结果：" + rs);
}
// 递归
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
postorder(root, res);
return res;
}
public void postorder(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
postorder(root.left, res);
postorder(root.right, res);
res.add(root.val);
}
// 非递归
public List<Integer> postorderTraversal02(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if (root == null) {
return res;
}
Deque<TreeNode> stack = new LinkedList<TreeNode>();
TreeNode prev = null;
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if (root.right == null || root.right == prev) {
res.add(root.val);
prev = root;
root = null;
} else {
stack.push(root);
root = root.right;
}
}
return res;
}运行结果：