두 갈래 나무의 비귀속 범람과 귀속 범람

문서 목록

앞말

전면 순차

귀속

비귀속

중순 스트리밍

귀속

비귀속

후순 반복

귀속

비귀속

층 서열 반복

전언
두 갈래 나무의 두루마리는 전 순서 두루마리, 중 순서 두루마리, 후속 순서 두루마리, 층 순서 두루마리가 있다.그런 다음 트리 노드의 정의는 다음과 같습니다.

class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }

    }

앞의 순서가 두루 미치다.
앞의 순서는 우리의 두 갈래 나무가 루트 노드를 먼저 훑어본 다음에 왼쪽 노드를 훑어보고 마지막은 오른쪽 노드를 훑어보는 것을 가리킨다
귀속

public void preOrder(TreeNode root){
        if (root == null){
            return;
        }
        // 
        System.out.println(root.val);
        // 
        preOrder(root.left);
        // 
        preOrder(root.right);
    }

비귀속

public void preOrder(TreeNode root){
        if (root == null){
            return;
        }
        // ， root.right ， root.left
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            System.out.println(node.val);
            if (node.right != null){
                stack.push(node.right);
            }
            if (node.left != null){
                stack.push(node.left);
            }
        }
    }

중순으로 두루 다니다.
귀속

public void midOrder(TreeNode root){
        if (root == null){
            return;
        }
        // 
        preOrder(root.left);
        // 
        System.out.println(root.val);
        // 
        preOrder(root.right);
    }

비귀속

public void midOrder(TreeNode root){
        if (root == null){
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        do {
            // ， 
            while (root != null){
                stack.push(root);
                root = root.left;
            }
            // ， ， ， 
            TreeNode node = stack.pop();
            System.out.println(node.val);
            if (node.right != null){
                root = node.right;
            }
        }while (root!= null || !stack.isEmpty());
    }

후순이 두루 다니다
귀속

public void afterOrder(TreeNode root){
        if (root == null){
            return;
        }

        // 
        preOrder(root.left);
        // 
        preOrder(root.right);
        // 
        System.out.println(root.val);
    }

비귀속

public void afterOrder(TreeNode root){
        if (root == null){
            return;
        }
        // ， root ， root s2 
        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();
        s1.push(root);
        while (!s1.isEmpty()){
            TreeNode node = s1.pop();
            if (node.left != null){
                s1.push(node.left);
            }
            if (node.right != null){
                s1.push(node.right);
            }
            s2.push(node);
        }
       while (!s2.isEmpty()){
           System.out.println(s2.pop().val);
       }

    }

차례차례
층차 스트리밍은 두 갈래 나무의 노드를 층층이 스트리밍하는 것을 가리킨다. 여기서 나는 노드를list에 저장하고 BFS 방식으로 노드를 스트리밍한다고 가정한다.

public List<List<Integer>> levelOrder(TreeNode root) {
		// 
        List<List<Integer>> lists = new ArrayList<>();
        if (root == null){
            return lists;
        }
        // 
        Queue<TreeNode> queue = new LinkedBlockingQueue<>();
        queue.add(root);
        while (!queue.isEmpty()){
            List<Integer> list = new ArrayList<>();
            int size = queue.size();
            // ， ， 
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null){
                    queue.add(node.left);
                }
                if (node.right != null){
                    queue.add(node.right);
                }
            }
            // list lists
            lists.add(list);
        }
        return lists;
    }