검지offer의 지그재그 순서로 두 갈래 나무 인쇄

18663 단어 검지 OFFER

검지offer의 지그재그 순서로 두 갈래 나무 인쇄

  • 제목 설명
  • 문제 풀이 사고방식
  • Code
  • 요약
  • 제목 설명


    함수는 지그재그로 두 갈래 트리를 인쇄합니다. 즉, 첫 번째 줄은 왼쪽에서 오른쪽으로, 두 번째 줄은 오른쪽에서 왼쪽으로, 세 번째 줄은 왼쪽에서 오른쪽으로, 다른 줄은 이와 같이 인쇄합니다.

    문제 풀이 사고방식


    나는 아마도 책을 보고 멍청한 것 같다. 책의 방법이 헷갈려서 창고를 쓰고 싶을 때, 왼쪽 나무를 먼저 저장하고 오른쪽 나무를 다음 층에 저장하고 반대로, 다행히 마지막에 냉정하게 분석하고 홀수층의 순서가 두루 흐르고, 짝수층은 창고를 사용한다.처음에 빈 바늘이 들어오는 상황을 주의하십시오.세그먼트 오류를 일으키다.

    Code

    /*
    struct TreeNode {
        int val;
        struct TreeNode *left;
        struct TreeNode *right;
        TreeNode(int x) :
                val(x), left(NULL), right(NULL) {
        }
    };
    */
    class Solution {
    public:
        vector<vector<int> > Print(TreeNode* pRoot) {
            vector<vector<int> > result;
            if(!pRoot) return result;
            vector<int> layer;
            queue<TreeNode*> q;
            stack<int> temps;
            int currentLayerCount = 1, nextLayerCount = 0, flag = 0;
            q.push(pRoot);
            while(!q.empty()) {
                TreeNode* currentTreeNode = q.front();
                q.pop();
                currentLayerCount--;
                if(flag) {
                    temps.push(currentTreeNode->val);
                } else {
                    layer.push_back(currentTreeNode->val);
                }
                if(currentTreeNode->left) {
                        q.push(currentTreeNode->left);
                        nextLayerCount++;
                }
                if(currentTreeNode->right) {
                        q.push(currentTreeNode->right);
                        nextLayerCount++;
                }
                if(!currentLayerCount) {
                    currentLayerCount = nextLayerCount;
                    nextLayerCount = 0;
                    if(flag) {
                        while(!temps.empty()) {
                            layer.push_back(temps.top());
                            temps.pop();
                        }
                    }
                    result.push_back(layer);
                    layer.clear();
                    flag = 1-flag;
                }
            } 
            return result;
        }
        
    };
    
  • java
  • import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.Collections;
    /*
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    */
    public class Solution {
        public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
            ArrayList<ArrayList<Integer> > result = new ArrayList<ArrayList<Integer> >();
            if(pRoot != null) {
                LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
                queue.add(pRoot);
                int currentCount = 1, currentLevel = 0, nextLayerCount = 0;
                ArrayList<Integer> layer = new ArrayList<Integer>();
                while(queue.size() > 0) {
                    TreeNode currentNode = queue.peek();
                    queue.pop();
                    layer.add(currentNode.val);
                    currentCount--;
                    if(currentNode.left != null) {
                        nextLayerCount++;
                        queue.add(currentNode.left);
                    }
                    if(currentNode.right != null) {
                        nextLayerCount++;
                        queue.add(currentNode.right);
                    }
                    if(currentCount == 0) {
                        currentCount = nextLayerCount;
                        nextLayerCount = 0;
                        if(currentLevel % 2 == 1) {
                            Collections.reverse(layer);
                        }
                        currentLevel++;
                        result.add(layer);
                        layer = new ArrayList<Integer>();
                    }
                }
            }
            return result;
        }
    
    }
    

    총결산

  • 직접reverse좋음
  • ArrayList 중 무작위 접근용get(index) 방법, 부치용set(index, value) 방법
  • Collections.reverse(list)좋아요
  • 좋은 웹페이지 즐겨찾기