笔记|对于二叉树的遍历问题数据结构|javascript|算法

目录

一、二叉树的前序遍历
1.1递归方法
1.2迭代方法
二、二叉树的中序遍历
2.1递归方法
2.2迭代方法
三、二叉树的后续遍历
【笔记|对于二叉树的遍历问题】3.1递归方法
3.2迭代方法
四、二叉树的逐层遍历
一、二叉树的前序遍历 1.1递归方法
对于前序遍历，我们一般采取根节点——根左子树——根右子树的方法来进行递归。
（1、

void preOrderTraversal(Node root){ if(root==null){ return; } System.out.println(root.val); preOrderTraversal(root.left); preOrderTraversal(root.right); }

(2、

//遍历思路 List list=new LinkedList<>(); public List preorderTraversal(TreeNode root) { if(root==null) return list; list.add(root.val); preorderTraversal(root.left); preorderTraversal(root.right); return list; }

（3、

//子问题思路 public List preorderTraversal(TreeNode root) { List list=new LinkedList<>(); if(root==null) return list; list.add(root.val); List listleft=preorderTraversal(root.left); list.addAll(listleft); List listright=preorderTraversal(root.right); list.addAll(listright); return list; }

1.2迭代方法
对于迭代来说我们会额外的加入一个栈，通过对于栈中是否有元素和元素的位置来判断

public List preorderTraversal(TreeNode root) { List list=new LinkedList<>(); if(root==null) return list; Stack stack=new Stack<>(); TreeNode cur=root; while (cur!=null||!stack.isEmpty()){ while (cur!=null){ list.add(cur.val); stack.push(cur); cur=cur.left; } cur=stack.pop(); cur=cur.right; } return list; }

二、二叉树的中序遍历 2.1递归方法
对于中序遍历，我们一般采取根左子树——根节点——根右子树的方法来进行递归。
（1、

void inOrderTraversal(Node root){ if(root==null) return; inOrderTraversal(root.left); System.out.println(root.val); inOrderTraversal(root.right); }

（2、

//遍历思路 List list=new LinkedList<>(); public List inorderTraversal(TreeNode root) { if(root==null) return list; inorderTraversal(root.left); list.add(root.val); inorderTraversal(root.right); return list; }

（3、

//子问题思路 public List inorderTraversal(TreeNode root) { List list=new LinkedList<>(); if(root==null) return list; List listleft=inorderTraversal(root.left); list.addAll(listleft); list.add(root.val); List listright=inorderTraversal(root.right); list.addAll(listright); return list; }

2.2迭代方法

public List inorderTraversal(TreeNode root) { List list=new LinkedList<>(); if(root==null) return list; Stack stack=new Stack<>(); while (!stack.isEmpty()||root!=null){ while (root!=null){ stack.add(root); root=root.left; } root=stack.pop(); list.add(root.val); root=root.right; } return list; }

三、二叉树的后续遍历 3.1递归方法
（1、

void postOrderTraversal(Node root){ if(root==null) return; postOrderTraversal(root.left); postOrderTraversal(root.right); System.out.println(root.val); }

（2、

//遍历思路 List list=new LinkedList<>(); public List postorderTraversal(TreeNode root) { if(root==null) return list; postorderTraversal(root.left); postorderTraversal(root.right); list.add(root.val); return list; }

（3、

//子问题思路 public List postorderTraversal(TreeNode root) { List list=new LinkedList<>(); if(root==null) return list; List listleft=postorderTraversal(root.left); list.addAll(listleft); List listright=postorderTraversal(root.right); list.addAll(listright); list.add(root.val); return list; }

3.2迭代方法

public List postorderTraversal(TreeNode root) { List list=new LinkedList<>(); if(root==null) return list; Stack stack=new Stack<>(); TreeNode cur=null; while (root!=null||!stack.isEmpty()){ while (root!=null){ stack.add(root); root=root.left; } root=stack.pop(); if(root.right==null||root.right==cur){ list.add(root.val); cur=root; root=null; }else { stack.push(root); root=root.right; } } return list; }

四、二叉树的逐层遍历将二叉树一层一层的遍历，通过队列来实现。
（1、

// 层序遍历 void levelOrderTraversal(TreeNode root){ if(root==null) return; Queue queue=new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()){ TreeNode temp=queue.poll(); System.out.println(temp.val+" "); if(temp.left!=null){ queue.offer(temp.left); }if(temp.right!=null){ queue.offer(temp.right); } } }

（2、

public List> levelOrder(TreeNode root) { List> list=new ArrayList<>(); if(root==null) return list; Queue queue=new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()){ int size=queue.size(); List list1=new ArrayList<>(); while (size!=0){ TreeNode temp=queue.poll(); list1.add(temp.val); if(temp.left!=null){ queue.add(temp.left); } if(temp.right!=null){ queue.add(temp.right); } size--; } list.add(list1); } return list; }