一、前序遍历（递归和非递归）
前序遍历就是先遍历根再遍历左之后是右 根左右
递归实现：
|
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