자바는 두 갈래 트리의 귀속, 비귀속을 실현하고 앞 순서, 중간 순서, 뒤 순서를 반복한다.차례차례

자바는 두 갈래 트리의 귀속, 비귀속을 실현하고 앞 순서, 중간 순서, 뒤 순서를 반복한다.차례차례
차례로 돌아가다

ArrayList<Integer> list = new ArrayList();
public ArrayList<Integer> preOrder(TreeNode root) {
	if (root != null) {
            list.add(root.val);
            preOrder(root.left);
            preOrder(root.right);
    }
    return list;
}	            

비귀속 전 순서 반복

	ArrayList<Integer> list = new ArrayList();
    public ArrayList<Integer> preOrder2(TreeNode root) {
        Stack<TreeNode> stack = new Stack();
        while (root != null || !stack.empty()) {
            while (root != null) {
                stack.push(root);
                list.add(root.val);
                root = root.left;
            }
            if (!stack.empty()) {
                root = stack.pop();
                root = root.right;
            }
        }
        return list;
    }

반복 반복

ArrayList<Integer> list = new ArrayList();
public ArrayList<Integer> preOrder(TreeNode root) {
	if (root != null) {
            preOrder(root.left);
        	list.add(root.val);
            preOrder(root.right);
    }
    return list;
}	

비귀속 중 순서 반복

	ArrayList<Integer> list = new ArrayList();
    public ArrayList<Integer> preOrder2(TreeNode root) {
        Stack<TreeNode> stack = new Stack();
        while (root != null || !stack.empty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            if (!stack.empty()) {
                root = stack.pop();
                list.add(root.val);
                root = root.right;
            }
        }
        return list;
    }

귀속 후 순서 반복 (첫 번째 해법)

ArrayList<Integer> list = new ArrayList();
public ArrayList<Integer> preOrder(TreeNode root) {
	if (root != null) {
            preOrder(root.left);
            preOrder(root.right);
        	list.add(root.val);
    }
    return list;
}

비귀속 후 순서 반복(두 번째 해법: 결점을 창고에서 꺼낼 때마다 오른쪽 결점이 앞의 결점인지 확인하고, 그렇다면 이 결점을 창고에서 꺼내야 한다)

import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode cur = root;
        TreeNode prior = null;
        ArrayList<Integer> ans = new ArrayList<Integer>(20);
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                if (cur.right == null || cur.right == prior) {
                    ans.add(cur.val);
                    prior = cur;
                    cur = null;
                }
                else {
                    stack.push(cur);
                    cur = cur.right;
                }
            }
        }
        return ans;
    }
}

비귀속 후차 범람(세 번째 해법: 앞차 범람을 중-> 오른쪽-> 왼쪽으로 바꾸고 리스트를 거꾸로 범람하면 바로 뒤차 범람: 왼쪽-> 오른쪽-> 중)

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new ArrayList();
        TreeNode prior = null;
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                list.add(root.val);
                root = root.right;
            }
            if (!stack.isEmpty()) {
                root = stack.pop();
                root = root.left;
            }
        }
        Collections.reverse(list);
        return list;
    }
}

반복되지 않은 계층:

public ArrayList<Integer> preOrder2(TreeNode root) {
        ArrayList<Integer> list = new ArrayList();
        Queue<TreeNode> queue = new LinkedList();
        queue.add(root);
        while (root != null || !queue.isEmpty()) {
            TreeNode node = queue.poll();
            list.add(node.val);
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
        return list;
    }

차례차례 차례로 두루 다니다.

class Solution {
    List<List<Integer>> levels = new ArrayList<List<Integer>>();

    public void helper(TreeNode node, int level) {
        // start the current level
        if (levels.size() == level)
            levels.add(new ArrayList<Integer>());

         // fulfil the current level
         levels.get(level).add(node.val);

         // process child nodes for the next level
         if (node.left != null)
            helper(node.left, level + 1);
         if (node.right != null)
            helper(node.right, level + 1);
    }
    
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) return levels;
        helper(root, 0);
        return levels;
    }
}