트리의 앞뒤 순차적 (귀속, 창고, 색 표시) ---Java 구현

10285 단어
두 갈래 트리의 앞뒤 순차적 (귀속, 창고) 자바 구현
카탈로그
  • 전면 순차
  • 중순 스트리밍
  • 후속 스트리밍
  • 색상 표기법(일반)
  • N 포크 나무의 앞 순서 반복
  • 귀속
  • 창고-교체
  • 색상 표기법
  • 참조 링크
  • 앞의 순서가 두루 미치다.


    리베이트
  • 귀속
  • import java.util.ArrayList;
    import java.util.List;
    
    public class PreOrder {
    
        public List preOrder(TreeNode root) {
            List res = new ArrayList<>();
    
            helper(root, res);
    
            return res;
        }
    
        public void helper(TreeNode root, List res) {
            if (root != null) {
                res.add(root.val);
    
                if (root.left != null) {
                    helper(root.left, res);
                }
    
                if (root.right != null) {
                    helper(root.right, res);
                }
    
            }
        }
    }
    
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x;}
    }
    
  • 스택
  • public List stackTravers_preorder(TreeNode root) {
            List res = new ArrayList<>();
            Stack stack = new Stack<>();
    
            TreeNode curr = root;
            while (curr != null || !stack.isEmpty()) {
                while (curr != null) {
                    res.add(curr.val);
                    stack.push(curr);
                    curr = curr.left;
                }
    
                if (!stack.isEmpty()) {
                    curr = stack.pop();
                    curr = curr.right;
    
                }
            }
    
            return res;
        }
    

    중순으로 두루 다니다.


    리베이트
  • 귀속
  • import java.util.ArrayList;
    import java.util.List;
    
    public class PreOrder {
    
        public List inorderTraversal(TreeNode root) {
            List res = new ArrayList<>();
            helper(root, res);
            return res;
        }
    
        // recursive
        public void helper(TreeNode root, List res) {
            if (root != null) {
                if (root.left != null) {
                    helper(root.left, res);
                }
    
                res.add(root.val);
    
                if (root.right != null) {
                    helper(root.right, res);
                }
    
            }
        }
    }
    
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x;}
    }
    
  • 스택
  • public List stackTraversl(TreeNode root) {
            List res = new ArrayList<>();
            Stack stack = new Stack<>();
    
            TreeNode curr = root;
            while (curr != null || !stack.isEmpty()) {
    
                // push the left tree into stack
                while (curr != null) {
                    stack.push(curr);
                    curr = curr.left;
                }
    
        		// when reached leaf node
                curr = stack.pop();
                res.add(curr.val);
                curr = curr.right;
            }
    
            return res;
        }
    

    뒤따르다


    감당하다
  • 귀속
  • import java.util.ArrayList;
    import java.util.List;
    
    public class PostOrder {
    
        public List postOrderTraversal(TreeNode root) {
            List res = new ArrayList<>();
            helper(root, res);
            return res;
        }
    
        // recursive
        public void helper(TreeNode root, List res) {
            if (root != null) {
                if (root.left != null) {
                    helper(root.left, res);
                }
                if (root.right != null) {
                    helper(root.right, res);
                }
                res.add(root.val);
            }
        }
    }
    
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x;}
    }
    
  • 스택
  • 알고리즘 핵심 사상: 먼저 선순, 중순, 후순의 비귀속 알고리즘의 공통점을 알아야 한다. 창고로 이전에 지나간 경로를 저장하여 서브트리에 방문한 후에 창고의 정보를 이용하여 현재 노드의 부모 노드로 되돌아와 다음 조작을 할 수 있도록 한다.뒷순서가 반복되는 비귀속 알고리즘은 세 가지 순서 중 가장 복잡한 것이다. 그 이유는 뒷순서가 왼쪽, 오른쪽 트리를 먼저 방문하고 다시 뿌리 노드를 방문하는 것이다. 비귀속 알고리즘에서 창고를 이용하여 뒤로 물러날 때 왼쪽 트리에서 뿌리 노드로 되돌아갈지, 오른쪽 트리에서 뿌리 노드로 되돌아갈지 모르기 때문이다. 만약에 왼쪽 트리에서 뿌리 노드로 되돌아간다면 이때 오른쪽 트리를 방문해야 한다. 만약에 오른쪽 트리에서 뿌리 노드로 되돌아간다면이 때 루트 노드에 접근해야 합니다.따라서 전서와 후서에 비해 창고를 닫을 때 정보를 추가해야 한다. 창고를 닫을 때 왼쪽 트리에서 돌아올지 오른쪽 트리에서 돌아올지 다음 동작을 결정할 수 있도록.저작권 성명: 본고는 CSDN 블로거'coder 666'의 오리지널 글로 CC4.0 BY-SA 저작권 협의에 따라 원문의 출처 링크와 본 성명을 옮겨 싣습니다.텍스트 링크:https://blog.csdn.net/coder__666/article/details/80349039
    public List stackTravers_postorder(TreeNode root) {
            List res = new ArrayList<>();
            Stack stack = new Stack<>();
            Stack stack2 = new Stack<>();      //  , , 
    
            TreeNode curr = root;
            int left = 1;  // note left tree
            int right = 2; // note right tree
    
            while (curr != null || !stack.isEmpty()) {
    
                while (curr != null) {
                    stack.push(curr);
                    stack2.push(left);
                    curr = curr.left;
                }
    
                while (!stack.isEmpty() && stack2.peek() == right) {
                    //  , , , 
                    stack2.pop();
                    res.add(stack.pop().val);
                }
    
                if (!stack.isEmpty() && stack2.peek() == left) {
                    //  , , 
                    //
                    stack2.pop();
                    stack2.push(right);
                    curr = stack.peek().right;
    
                }
    
            }
    
    
            return res;
        }
    

    색상 표기법(일반)


    색 표기법
    public class ColorMethod {
    
        //  
        class ColorNode{
            TreeNode node;
            int color;
    
            public ColorNode(TreeNode node, int color) {
                this.node = node;
                this.color = color;
            }
        }
        
        class TreeNode {
            int val;
            TreeNode left;
            TreeNode right;
            TreeNode(int x) { val = x;}
    	}
    
        private final int white = 0;
        private final int gray = 1;
    
    
        public List inorderTraversal(TreeNode root) {
            List res = new ArrayList<>();
    
            if (root == null) {
                return res;
            }
    
            Stack stack = new Stack<>();
            stack.push(new ColorNode(root, white));
    
            while (!stack.isEmpty()) {
                ColorNode curr = stack.pop();
    
                //  
                if (curr.color == white) {
                    if (curr.node.right != null) {
                        stack.push(new ColorNode(curr.node.right, white));
                    }
                    //  
                    stack.push(new ColorNode(curr.node, gray));
                    if (curr.node.left != null) {
                        stack.push(new ColorNode(curr.node.left, white));
                    }
                } else {
                    res.add(curr.node.val);
                }
    
            }
            return res;
        }
    
    
    }
    

    N 포크 트리의 앞 순서 반복


    공제하다

    귀속

    /**
     * N 
     */
    public class Recursive {
    
        //  
        public List preorder(Node root) {
            List res = new ArrayList<>();
            if (root == null) {
                return res;
            }
            helper(root, res);
            return res;
        }
    
        private void helper(Node curr, List res) {
            if (curr != null) {
                res.add(curr.val);
                for (Node temp : curr.children) {
                    helper(temp, res);
                }
            }
        }
    
    }
    
    class Node {
        public int val;
        public List children;
    
        public Node() {}
    
        public Node(int _val) {
            val = _val;
        }
    
        public Node(int _val, List _children) {
            val = _val;
            children = _children;
        }
    }
    

    스택 - 반복

    /**
     *  , , 
     */
    public class StackIterator {
    
        public List preorder(Node root) {
    //        List stack = new LinkedList<>();
            Stack stack = new Stack<>();
            List res = new LinkedList<>();
    
            if (root == null) {
                return res;
            }
    
            stack.add(root);
    
            while (!stack.isEmpty()) {
                //  , root left tight
                //  
                Node curr = stack.pop();
                res.add(curr.val);
                if (curr.children != null) {
                    Collections.reverse(curr.children);
                    for (Node temp : curr.children) {
                        stack.push(temp);
                    }
                }
            }
    
            return res;
        }
    

    색 표기법

    public class ColorMethod {
    
        private final int white = 0;
        private final int gray = 1;
    
        public List preorder(Node root) {
            List res = new LinkedList<>();
    
            if (root == null) {
                return res;
            }
    
            Stack stack = new Stack<>();
            stack.push(new ColorNode(root, white));
    
            while (!stack.isEmpty()) {
                ColorNode curr = stack.pop();
    
                if (curr.color == white) {
                    //  
                    if (curr.node.children != null) {
                        Collections.reverse(curr.node.children);
                        for (Node temp : curr.node.children) {
                            stack.push(new ColorNode(temp, white));
                        }
                        stack.push(new ColorNode(curr.node, gray));
                    }
                } else {
                    res.add(curr.node.val);
                }
            }
    
            return res;
        }
    
    
    }
    
    
    class Node {
        public int val;
        public List children;
    
        public Node() {}
    
        public Node(int _val) {
            val = _val;
        }
    
        public Node(int _val, List _children) {
            val = _val;
            children = _children;
        }
    }
    
    //  
    class ColorNode{
        Node node;
        int color;
    
        public ColorNode(Node node, int color) {
            this.node = node;
            this.color = color;
        }
    }
    

    참조 링크


    CSDN
    역단추 중 순서대로 문제풀이를 두루 훑어보다
    힘줄 문제풀이-색 표기법

    좋은 웹페이지 즐겨찾기