1、前序遍历
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> lists = new ArrayList<>();
if (root == null) return lists;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
TreeNode temp = null;
while (!stack.isEmpty()) {
temp = stack.pop();
lists.add(temp.val);
// 这里注意，要先压入右子节点，再压入左节点
if (temp.right != null) {
stack.push(temp.right);
}
if (temp.left != null) {
stack.push(temp.left);
}
}
return lists;
}
2、中序遍历
public List<Integer> inorderTraversal(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root, temp = null;
List<Integer> lists = new ArrayList<>();
// 判断条件：所有栈为空，且节点指向为空，即所有节点已经完成遍历
while (!stack.isEmpty() || node != null) {
// 向左搜索，寻找最左的节点，即中序遍历的第一个节点
while (node != null) {
stack.add(node);
node = node.left;
}
// 对每一个节点进行判断
if (!stack.empty()) {
// 获取当前节点
temp = stack.pop();
// 遍历该节点
lists.add(temp.val);
// 如果该节点为内部节点，则按中序遍历的顺序，遍历其右子节点
node = temp.right;
}
}
return lists;
}
3、后续遍历
public List<Integer> postorderTraversal_(TreeNode root) {
LinkedList<Integer> lists = new LinkedList<>();
if (root == null) return lists;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
TreeNode temp = null;
while (!stack.isEmpty()) {
temp = stack.pop();
lists.add(temp.val);
if (temp.left != null) {
stack.push(temp.left);
}
if (temp.right != null) {
stack.push(temp.right);
}
}
return lists;
}