LeetCode 94、144、145 中序、前序、后序遍历递归算法非递归算法
在Java中list既可以实现栈,也可以实现队列。后序遍历的非递归算法,是难一点儿。
前序遍历:
递归算法:
- public class LC144Try1
- {
- public List<Integer> preorderTraversal(TreeNode root)
- {
- List<Integer> arr=new ArrayList<Integer>();
- prePass(root,arr);
- return arr;
- }
- public void prePass(TreeNode root,List<Integer> arr){
- if(root==null){
- return;
- }
- arr.add(root.val);
- prePass(root.left,arr);
- prePass(root.right,arr);
- }
- }
非递归算法:
- package test;
- import java.util.ArrayList;
- import java.util.List;
- //非递归算法
- public class LC144Try2
- {
- public List<Integer> preorderTraversal(TreeNode root)
- {
- List<Integer> arr = new ArrayList<Integer>();
- List<TreeNode> list= new ArrayList<TreeNode>();
- TreeNode p=root;
- while(p!=null || list.size()>0){
- if(p!=null){
- arr.add(p.val);
- list.add(p);
- p=p.left;
- }else{
- p=list.remove(list.size()-1);
- p=p.right;
- }
- }
- return arr;
- }
- public static void main(String[] args)
- {
- LC144Try2 t = new LC144Try2();
- TreeNode root= new TreeNode(1);
- TreeNode r1= new TreeNode(2);
- TreeNode r2= new TreeNode(3);
- root.right=r1;
- r1.right=r2;
- System.out.println(t.preorderTraversal(root));
- }
- }
中序遍历
递归算法:
- package test;
- import java.util.ArrayList;
- import java.util.List;
- class TreeNode {
- int val;
- TreeNode left;
- TreeNode right;
- TreeNode(int x) { val = x; }
- }
- //递归
- public class LC94Try1
- {
- public List<Integer> inorderTraversal(TreeNode root) {
- List<Integer> arr = new ArrayList<Integer>();
- inorderPass(root,arr);
- return arr;
- }
- public void inorderPass(TreeNode root,List<Integer> arr){
- if(root==null){
- return;
- }
- inorderPass(root.left,arr);
- arr.add(root.val);
- inorderPass(root.right,arr);
- }
- }
非递归算法:
- package test;
- import java.util.ArrayList;
- import java.util.List;
- //非递归
- public class LC94Try2
- {
- public List<Integer> inorderTraversal(TreeNode root)
- {
- List<Integer> arr = new ArrayList<Integer>();
- List<TreeNode> list = new ArrayList<TreeNode>();
- TreeNode p = root;
- while (p != null || list.size() > 0)
- {
- if (p != null)
- {
- list.add(p);
- p = p.left;
- }else{
- p=list.remove(list.size()-1);
- arr.add(p.val);
- p=p.right;
- }
- }
- return arr;
- }
- }
后序遍历:
递归算法:
- package test;
- import java.util.ArrayList;
- import java.util.List;
- public class LC145Try1
- {
- public List<Integer> postorderTraversal(TreeNode root)
- {
- List<Integer> arr = new ArrayList<Integer>();
- postorderPass(root,arr);
- return arr;
- }
- public void postorderPass(TreeNode root,List<Integer> arr){
- if(root==null){
- return;
- }else{
- postorderPass(root.left,arr);
- postorderPass(root.right,arr);
- arr.add(root.val);
- }
- }
- }
非递归算法:
- package test;
- import java.util.ArrayList;
- import java.util.List;
- public class LC145Try2
- {
- public List<Integer> postorderTraversal(TreeNode root)
- {
- List<Integer> arr = new ArrayList<Integer>();
- List<TreeNode> list = new ArrayList<TreeNode>();
- TreeNode p = root;
- TreeNode r = root;//上一次读取的位置
- while(p!=null || list.size()>0){
- if(p!=null){
- list.add(p);
- p=p.left;
- }else{
- p=list.get(list.size()-1);
- if(p.right!=null && p.right!=r){
- p=p.right;
- }else{
- r=p;
- arr.add(p.val);
- list.remove(list.size()-1);
- p=null;
- }
- }
- }
- return arr;
- }
- }
哈哈
相关推荐
steeven 2020-11-10
Tips 2020-10-14
nongfusanquan0 2020-08-18
yedaoxiaodi 2020-07-26
清溪算法君老号 2020-06-27
pengkingli 2020-06-25
yishujixiaoxiao 2020-06-25
清溪算法 2020-06-21
RememberMePlease 2020-06-17
nurvnurv 2020-06-05
SystemArchitect 2020-06-02
码墨 2020-05-29
清溪算法 2020-05-27
choupiaoyi 2020-05-27
清溪算法 2020-05-25
bluewelkin 2020-05-19
dbhllnr 2020-05-15
steeven 2020-05-09
baike 2020-05-09