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