前言
2023-8-7 15:13:50
以下内容源自《【创作模板五】》
仅供学习交流使用
版权
禁止其他平台发布时删除以下此话
本文首次发布于CSDN平台
作者是CSDN@日星月云
博客主页是https://blog.csdn.net/qq_51625007
禁止其他平台发布时删除以上此话
推荐
二叉树的遍历【学习算法】
先序遍历
递归实现
class Solution { public List<Integer> preorderTraversal(TreeNode root) { ArrayList<Integer> res=new ArrayList<>(); preorderTraversal(root,res); return res; } public void preorderTraversal(TreeNode root,ArrayList<Integer> list) { if(root!=null){ list.add(root.val); preorderTraversal(root.left,list); preorderTraversal(root.right,list); } } }
递归非实现-1
class Solution { public List<Integer> preorderTraversal(TreeNode root) { ArrayList<Integer> res=new ArrayList<>(); preorderTraversal(root,res); return res; } public void preorderTraversal(TreeNode root,ArrayList<Integer> list) { Stack<TreeNode> stack=new Stack<>(); TreeNode cur=root; while(cur!=null||!stack.isEmpty()){ while(cur!=null){ list.add(cur.val); stack.push(cur); cur=cur.left; } if(!stack.isEmpty()){ cur=stack.pop(); cur=cur.right; } } } }
递归非实现-2
class Solution { public List<Integer> preorderTraversal(TreeNode root) { ArrayList<Integer> res=new ArrayList<>(); preorderTraversal(root,res); return res; } public void preorderTraversal(TreeNode root,ArrayList<Integer> list) { Stack<TreeNode> stack=new Stack<>(); TreeNode cur=root; while(cur!=null||!stack.isEmpty()){ if(cur!=null){ list.add(cur.val); stack.push(cur); cur=cur.left; }else{ cur=stack.pop(); cur=cur.right; } } } }
中序遍历
递归实现
class Solution { //递归 public List<Integer> inorderTraversal(TreeNode root) { ArrayList<Integer> res=new ArrayList<>(); inorderTraversal(root,res); return res; } public void inorderTraversal(TreeNode root,ArrayList<Integer> list) { if(root!=null){ inorderTraversal(root.left,list); list.add(root.val); inorderTraversal(root.right,list); } } }
非递归实现-1
class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> list=new ArrayList<>(); Stack<TreeNode> stack=new Stack(); TreeNode cur=root; while(cur!=null||!stack.isEmpty()){//当前结点指针及栈均空,则结束 while(cur!=null){//访问根结点,根指针进栈,进入左子树 stack.push(cur); cur=cur.left; } if(!stack.isEmpty()){ cur=stack.pop(); list.add(cur.val); cur=cur.right;//根指针退栈,进入其右子树 } } return list; } }
非递归实现-2
class Solution { //递归 public List<Integer> inorderTraversal(TreeNode root) { ArrayList<Integer> res=new ArrayList<>(); inorderTraversal(root,res); return res; } public void inorderTraversal(TreeNode root,ArrayList<Integer> list) { Stack<TreeNode> stack=new Stack<>(); TreeNode cur=root; //结点不为空或栈不为空 while(cur!=null||!stack.isEmpty()){ //结点不为空 if(cur!=null){ stack.push(cur); cur=cur.left; }else{ cur=stack.pop(); list.add(cur.val); cur=cur.right; } } } }
后序遍历
递归
class Solution { public List<Integer> postorderTraversal(TreeNode root) { ArrayList<Integer> res=new ArrayList<>(); postorderTraversal(root,res); return res; } public void postorderTraversal(TreeNode root,ArrayList<Integer> list) { if(root!=null){ postorderTraversal(root.left,list); postorderTraversal(root.right,list); list.add(root.val); } } }
非递归
class Solution { public List<Integer> postorderTraversal(TreeNode root) { ArrayList<Integer> res=new ArrayList<>(); Stack<TreeNode> stack=new Stack<>(); TreeNode cur=root,next=null; while(cur!=null||!stack.isEmpty()){ //先把结点给全进栈 while(cur!=null){ stack.push(cur); cur=cur.left;//左 } //栈不为空 if(!stack.isEmpty()){ cur=stack.peek(); if(cur.right==null||cur.right==next){ //判断栈顶结点的右子树是否为空，或者刚被访问过 cur=stack.pop(); res.add(cur.val);//根 next=cur;//记录刚访问 cur=null;//清空 }else{ cur=cur.right;//右 } } } return res; } }
最后
2023-8-7 16:00:45
我们都有光明的未来
祝大家考研上岸
祝大家工作顺利
祝大家得偿所愿
祝大家如愿以偿
点赞收藏关注哦
