ツリーの前順序、中順序、後続、階層遍歴統一アルゴリズム

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;
    }
}

参照:カラータグ法-一般的で簡明なツリー遍歴方法