二叉树的前序、中序、后序、层序遍历,非递归实现
程序员文章站
2022-05-16 14:37:27
...
二叉树的遍历
二叉树的前中后遍历使用递归比较简单,这里只介绍非递归的方式
前序 :根左右
中序 :左根右
后序 :左右根
层序 :按层
1、前序遍历
给你二叉树的根节点 root ,返回它节点值的 前序 遍历。LeetCode144
使用栈先进后出的特点,每碰到一个结点,先记录此节点,再尽可能的寻早右节点入栈,最后将左节点入栈
public class LeetCode_144 {
public List<Integer> preorderTraversal(TreeNode root) {
if (root == null) return null;
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.pop();
list.add(node.val);
if (node.right!=null){
stack.push(node.right);
}
if (node.left!=null){
stack.push(node.left);
}
}
return list;
}
}
2、中序遍历
给定一个二叉树的根节点 root ,返回它的 中序 遍历。 LeetCode94
先将左节点都入栈,然后记录结点的值,再将右节点入栈
public class LeetCode_94 {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null) return list;
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || root != null){
while (root != null){
stack.push(root);
root = root.left;
}
TreeNode node = stack.pop();
list.add(node.val);
if (node.right != null){
root = node.right;
}
}
return list;
}
}
3、后序遍历
给定一个二叉树的根节点 root ,返回它的 后序 遍历。LeetCode145
public class LeetCode_145 {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null) return list;
Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>();
stack1.push(root);
while (!stack1.isEmpty()){
TreeNode node = stack1.pop();
stack2.push(node);
if (node.left != null){
stack1.push(node.left);
}
if (node.right != null){
stack1.push(node.right);
}
}
while (!stack2.empty()){
TreeNode node = stack2.pop();
list.add(node.val);
}
return list;
}
}
4、层序遍历
给定一个二叉树的根节点 root ,返回它的 层序遍历。LeetCode102
public class LeetCode_102 {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> lists = new ArrayList<>();
List<Integer> list = new ArrayList<>();
if (root == null) return lists;
//记录每层的元素个数,默认第一层元素个数为1
int size = 1;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
TreeNode node = queue.poll();
size --;
list.add(node.val);
if (node.left!=null){
queue.offer(node.left);
}
if (node.right != null){
queue.offer(node.right);
}
if (size == 0){
size = queue.size();
lists.add(list);
list = new ArrayList<>();
}
}
return lists;
}
}
推荐阅读