一、前序遍历（递归和非递归）
前序遍历就是先遍历根再遍历左之后是右 根左右
递归实现：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
public List<Integer> preorderTraversal(TreeNode root) { List <Integer> list=new ArrayList<>(); pre(root,list); return list; } public void pre(TreeNode root,List list){ if(root==null){ return ; } list.add(root.val); pre(root.left,list); pre(root.right,list); } |
迭代实现：
利用栈来实现 先将树的右子树放入栈中，再放入左子树
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
public List<Integer> preorderTraversal(TreeNode root) { List<Integer> list=new LinkedList<>(); if(root==null) return list; 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; } |
二、中序遍历（递归和非递归）
中序遍历就是先遍历左再遍历根，最后遍历右 左根右
递归实现：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
public List<Integer> inorderTraversal(TreeNode root) { List <Integer> list=new ArrayList<>(); inorder(root,list); return list; } public void inorder(TreeNode root,List list){ if(root==null){ return ; } inorder(root.left,list); list.add(root.val); inorder(root.right,list); } |
迭代实现
利用栈来实现，二叉树的中序遍历，由于中序遍历是左根右，先定义节点找到最左节点入栈，之后出栈，判断该节点是否有右孩子
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
public List<Integer> inorderTraversal(TreeNode root) { //迭代实现 List<Integer> list =new LinkedList<>(); Stack <TreeNode> stack=new Stack<>(); TreeNode cur=root; while(cur!=null||!stack.isEmpty()){ //先找到左节点 while(cur!=null){ stack.push(cur); cur=cur.left; } TreeNode node=stack.pop(); list.add(node.val); if(node.right!=null){ cur=node.right; } } return list; } |
三、后序遍历（递归和非递归）
后序遍历就是左右根
递归实现：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
public List<Integer> postorderTraversal(TreeNode root) { List<Integer> list=new ArrayList<>(); postorder(root,list); return list; } public void postorder(TreeNode root,List list){ if(root==null){ return ; } postorder(root.left,list); postorder(root.right,list); list.add(root.val); } |
非递归实现：
用两个栈来实现二叉树的后序遍历
第一个栈先放入根节点，之后弹出放入第二个节点，之后第一个栈放入左右孩子，之后再弹出放入第二个栈，即可实现
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
public List<Integer> postorderTraversal(TreeNode root) { //利用双栈实现后序遍历 Stack <TreeNode> s1=new Stack<>(); Stack <TreeNode> s2=new Stack<>(); List<Integer> list=new LinkedList<>(); if(root==null) return list; s1.push(root); while(!s1.isEmpty()){ TreeNode node=s1.pop(); s2.push(node); if(node.left!=null) s1.push(node.left); if(node.right!=null) s1.push(node.right); } while(!s2.isEmpty()){ TreeNode cur=s2.pop(); list.add(cur.val); } return list; } |
四、层序遍历
用队列实现层序遍历
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
public List<List<Integer>> levelOrder(TreeNode root) { //用队列实现层序遍历 //第一层节点先进队列，出的节点带下一层的节点 List <List<Integer>> list=new ArrayList<>(); if(root==null) return list; Queue<TreeNode> queue=new LinkedList<>(); queue.offer(root); while(!queue.isEmpty()){ List<Integer> list1=new ArrayList<>(); int size=queue.size(); while(size!=0){ TreeNode cur=queue.poll(); list1.add(cur.val); if(cur.left!=null){ queue.offer(cur.left); } if(cur.right!=null){ queue.offer(cur.right); } size--; } list.add(list1); } return list; } |
总结
本篇文章就到这里了，希望能给你带来帮助，也希望你能够多多关注服务器之家的更多内容！
原文链接：https://blog.csdn.net/weixin_51601437/article/details/119279741
