对应LeetCode：144、94、145
一、二叉树的前序遍历
1、递归
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
List<Integer> re = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
preOrder(root);
return re;
}
private void preOrder(TreeNode root) {
if (root == null) {
return;
}
re.add(root.val);
preOrder(root.left);
preOrder(root.right);
}
}
2、迭代
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> re = new ArrayList<>();
if (root == null) {
return re;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode temp = stack.pop();
re.add(temp.val);
if (temp.right != null) {
stack.push(temp.right);
}
if (temp.left != null) {
stack.push(temp.left);
}
}
return re;
}
}
3、通用解法（模拟系统栈指令）
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private class Command {
String s;
TreeNode node;
Command(String s, TreeNode node) {
this.s = s;
this.node = node;
}
}
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> re = new ArrayList<>();
if (root == null) {
return re;
}
Stack<Command> stack = new Stack<>();
stack.push(new Command("go", root));
while (!stack.isEmpty()) {
Command command = stack.pop();
if (command.s.equals("print")) {
re.add(command.node.val);
} else {
if (command.node.right != null) {
stack.push(new Command("go", command.node.right));
}
if (command.node.left != null) {
stack.push(new Command("go", command.node.left));
}
stack.push(new Command("print", command.node));
}
}
return re;
}
}
二、二叉树的中序遍历
1、递归
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
List<Integer> re = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
inOrder(root);
return re;
}
private void inOrder(TreeNode root) {
if (root == null) {
return;
}
inOrder(root.left);
re.add(root.val);
inOrder(root.right);
}
}
2、迭代
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> re = new ArrayList<>();
if (root == null) {
return re;
}
Stack<TreeNode> stack = new Stack<>();
while (root != null || !stack.isEmpty()) {
if (root != null) {
stack.push(root);
root = root.left;
} else {
root = stack.pop();
re.add(root.val);
root = root.right;
}
}
return re;
}
}
3、通用解法（模拟系统栈指令）
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private class Command {
String s;
TreeNode node;
Command(String s, TreeNode node) {
this.s = s;
this.node = node;
}
}
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> re = new ArrayList<>();
if (root == null) {
return re;
}
Stack<Command> stack = new Stack<>();
stack.push(new Command("go", root));
while (!stack.isEmpty()) {
Command command = stack.pop();
if (command.s.equals("print")) {
re.add(command.node.val);
} else {
if (command.node.right != null) {
stack.push(new Command("go", command.node.right));
}
stack.push(new Command("print", command.node));
if (command.node.left != null) {
stack.push(new Command("go", command.node.left));
}
}
}
return re;
}
}
三、二叉树的后序遍历
1、递归
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
List<Integer> re = new ArrayList<>();
public List<Integer> postorderTraversal(TreeNode root) {
afterOrder(root);
return re;
}
private void afterOrder(TreeNode root) {
if (root == null) {
return;
}
afterOrder(root.left);
afterOrder(root.right);
re.add(root.val);
}
}
2、迭代
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> re = new ArrayList<>();
if (root == null) {
return re;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode pre = null;
stack.push(root);
while (!stack.isEmpty()) {
TreeNode cur = stack.peek();
// 如果当前结点左右子节点为空或上一个访问的结点为当前结点的子节点时，当前结点出栈
if ((cur.left == null && cur.right == null) || (pre != null && (pre == cur.left || pre == cur.right))) {
re.add(cur.val);
pre = cur;
stack.pop();
} else {
if (cur.right != null) {
stack.push(cur.right);
}
if (cur.left != null) {
stack.push(cur.left);
}
}
}
return re;
}
}
3、通用解法（模拟系统栈指令）
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private class Command {
String s;
TreeNode node;
Command(String s, TreeNode node) {
this.s = s;
this.node = node;
}
}
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> re = new ArrayList<>();
if (root == null) {
return re;
}
Stack<Command> stack = new Stack<>();
stack.push(new Command("go", root));
while (!stack.isEmpty()) {
Command command = stack.pop();
if (command.s.equals("print")) {
re.add(command.node.val);
} else {
stack.push(new Command("print", command.node));
if (command.node.right != null) {
stack.push(new Command("go", command.node.right));
}
if (command.node.left != null) {
stack.push(new Command("go", command.node.left));
}
}
}
return re;
}
}