二叉树前序，中序，后续，层次遍历统一的算法

桃扇骨 2023-03-13 05:15 15阅读 0赞

public class TreeNode {  //二叉树节点定义
          int val;
         TreeNode left;
         TreeNode right;
          TreeNode(int x) {  val = x; }
      }

一：前序遍历

import java.util.ArrayDeque;
    import java.util.ArrayList;
    import java.util.Deque;
    import java.util.List;
    
    class Solution { 
    	class ColorNode { 
            TreeNode node;
            char color;
            
            public ColorNode(TreeNode node,char color){ 
                this.node = node;
                this.color = color;
            }
        }
    	
    	
        public List<Integer> preorderTraversal(TreeNode root) { 
        	List<Integer> ans = new ArrayList();
        	if(root == null) return ans;
        	Deque<ColorNode> stack = new ArrayDeque();
        	stack.addLast(new ColorNode(root, '0'));
        	
        	while(!stack.isEmpty()) { 
        		ColorNode cur = stack.pollLast();
        		if(cur.color == '0') { 
    				
        			if(cur.node.right != null) { 
    	    			stack.addLast(new ColorNode(cur.node.right, '0'));
        			}
        			
        			if(cur.node.left != null) { 
        				stack.addLast(new ColorNode(cur.node.left, '0'));
        			}
    
    				stack.addLast(new ColorNode(cur.node, '1'));
    				
        		}else { 
        			ans.add(cur.node.val);
        		}
        	}
        	return ans;
        }
    }

二：中序遍历

import java.util.ArrayDeque;
    import java.util.ArrayList;
    import java.util.Deque;
    import java.util.List;
    
    class Solution { 
    	class ColorNode { 
            TreeNode node;
            char color;
            
            public ColorNode(TreeNode node,char color){ 
                this.node = node;
                this.color = color;
            }
        }
    	
    	
        public List<Integer> inorderTraversal(TreeNode root) { 
        	List<Integer> ans = new ArrayList();
        	if(root == null) return ans;
        	Deque<ColorNode> stack = new ArrayDeque();
        	stack.addLast(new ColorNode(root, '0'));
        	
        	while(!stack.isEmpty()) { 
        		ColorNode cur = stack.pollLast();
        		if(cur.color == '0') { 
        			if(cur.node.right != null) { 
    	    			stack.addLast(new ColorNode(cur.node.right, '0'));
        			}
        			stack.addLast(new ColorNode(cur.node, '1'));
        			if(cur.node.left != null) { 
        				stack.addLast(new ColorNode(cur.node.left, '0'));
        			}
        		}else { 
        			ans.add(cur.node.val);
        		}
        	}
        	return ans;
        }
    }

三：后序遍历

import java.util.ArrayDeque;
    import java.util.ArrayList;
    import java.util.Deque;
    import java.util.List;
    
    class Solution { 
    	class ColorNode { 
            TreeNode node;
            char color;
            
            public ColorNode(TreeNode node,char color){ 
                this.node = node;
                this.color = color;
            }
        }
    	
    	
        public List<Integer> postorderTraversal(TreeNode root) { 
        	List<Integer> ans = new ArrayList();
        	if(root == null) return ans;
        	Deque<ColorNode> stack = new ArrayDeque();
        	stack.addLast(new ColorNode(root, '0'));
        	
        	while(!stack.isEmpty()) { 
        		ColorNode cur = stack.pollLast();
        		if(cur.color == '0') { 
        			stack.addLast(new ColorNode(cur.node, '1'));
        			
        			if(cur.node.right != null) { 
    	    			stack.addLast(new ColorNode(cur.node.right, '0'));
        			}
        			
        			if(cur.node.left != null) { 
        				stack.addLast(new ColorNode(cur.node.left, '0'));
        			}
        		}else { 
        			ans.add(cur.node.val);
        		}
        	}
        	return ans;
        }
    }

四：层次遍历

import java.util.ArrayDeque;
    import java.util.ArrayList;
    import java.util.Deque;
    import java.util.List;
    
    class Solution { 
    	class ColorNode { 
            TreeNode node;
            char color;
            int lev;
            
            public ColorNode(TreeNode node,char color,int lev){ 
                this.node = node;
                this.color = color;
                this.lev = lev;
            }
        }
    	
    	
        public List<List<Integer>> levelderTraversal(TreeNode root) { 
        	List<List<Integer>> ans = new ArrayList();
        	if(root == null) return ans;
        	Deque<ColorNode> stack = new ArrayDeque();
        	stack.addLast(new ColorNode(root, '0', 0));
        	
        	while(!stack.isEmpty()) { 
        		ColorNode cur = stack.pollLast();
        		int lev = cur.lev;
        		if(cur.color == '0') { 
        			if(cur.node.right != null) { 
    	    			stack.addLast(new ColorNode(cur.node.right, '0', lev+1));
        			}
        			if(cur.node.left != null) { 
        				stack.addLast(new ColorNode(cur.node.left, '0', lev+1));
        			}
        			stack.addLast(new ColorNode(cur.node, '1', lev));
        		}else { 
        			if(lev == ans.size()) ans.add(new ArrayList());
        			ans.get(lev).add(cur.node.val);
        		}
        	}
        	return ans;
        }
    }

参考：[颜色标记法-一种通用且简明的树遍历方法][-]

[-]: https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/yan-se-biao-ji-fa-yi-chong-tong-yong-qie-jian-ming/