두 갈래 나무 관련 문제 풀이 세트

폭 우선 반복(BFS: Breath First Search), 깊이 우선 반복(DFS: Depth First Search), 폭 우선 (층별) 반복 대기열, 깊이 우선 반복 우선 반복, 창고의 실현은 반복보다 복잡하다

주의점

줄 바꾸기 인쇄는 두 가지 지침이 필요합니다. 하나는 현재 줄을 저장하는 가장 오른쪽 노드, 하나는 다음 줄의 가장 최근에 가입한 노드를 추적합니다. 앞줄의 가장 오른쪽 노드가 튀어나올 때 다음 줄의 가장 최근에 가입한 노드로 업데이트하면 이 줄은 다음 줄의 노드와 구분할 수 있습니다

지그재그 인쇄 체인 테이블은 세 개의 지침이 필요합니다. 하나는 현재 줄이 대기열에서 마지막으로 튀어나온 노드를 저장하고, 하나는 오른쪽으로 한 줄을 저장하고, 하나는 왼쪽으로 한 줄을 저장하는 가장 왼쪽 노드를 저장합니다.홀수행 대기열은 팀 헤더를 팝업하고 팀 끝에 새 노드를 추가합니다. 먼저 왼쪽 노드를 추가한 다음에 오른쪽 노드를 추가합니다.짝수 줄 대기열은 대열의 끝을 팝업하고 대열에 새 노드를 추가합니다. 먼저 오른쪽 노드를 추가한 다음에 왼쪽 노드를 추가합니다

카탈로그

위에서 아래로 두 갈래 나무를 인쇄한다

두 갈래 나무를 여러 줄로 인쇄한다

지그재그 순서로 두 갈래 나무를 인쇄한다(어려우니 연습이 필요하다)

두 갈래 트리를 서열화한다(bugfree는 할 수 없고 연습이 필요하다)

위에서 아래로 두 갈래 나무를 인쇄하다

위에서 아래로 두 갈래 나무의 각 노드를 인쇄하고, 같은 층의 노드는 왼쪽에서 오른쪽으로 인쇄합니다.

public ArrayList PrintFromTopToBottom(TreeNode root) {
    ArrayList res = new ArrayList<>();
    if (root == null) {
        return res;
    }
    LinkedList queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode p = queue.poll();
        res.add(p.val);
        if (p.left != null) {
            queue.add(p.left);
        }
        if (p.right != null) {
            queue.add(p.right);
        }
    }
    return res;
}

두 갈래 나무를 여러 줄로 인쇄하다

위에서 아래로 층별로 두 갈래 트리를 인쇄하고 같은 층의 결점은 왼쪽에서 오른쪽으로 출력합니다.층마다 줄을 출력합니다.

두 갈래 나무는 층별로 인쇄하는데 반드시 대열로 이루어진다

ArrayList> Print(TreeNode pRoot) {
    ArrayList> res = new ArrayList<>();
    ArrayList list = new ArrayList<>();
    if (pRoot == null) {
        res.add(list);
        return res;
    }
    LinkedList queue = new LinkedList<>();
    queue.add(pRoot);
    // last  ，nlast 
    TreeNode last = pRoot, nlast = pRoot;
    while (!queue.isEmpty()) {
        TreeNode p = queue.poll();
        list.add(p);
        if (p.left != null) {
            queue.add(p.left);
            nlast = p.left;
        }
        if (p.right != null) {
            queue.add(p.right);
            nlast = p.right;
        }
        //  last ， 
        // last nlast， 
        if (p == last) {
            last = nlast;
            res.add(list);
            list = new ArrayList<>();
        }
    }
    return res;
}

지그재그 순서로 두 갈래 나무를 인쇄하다

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

쌍방향 체인 시계, 홀수층이 대열에 원소를 첨가하고 대열을 튀긴다.짝수 레이어는 대열의 끝에 요소를 추가하고 대열의 끝을 팝업합니다.left는 짝수층이 맨 왼쪽에 도착하는지,right는 홀수층이 맨 오른쪽에 도착하는지 감시합니다

public ArrayList> Print(TreeNode pRoot) {
    ArrayList> res = new ArrayList<>();
    ArrayList list = new ArrayList<>();
    if (pRoot == null) {
        return res;
    }
    LinkedList queue = new LinkedList();
    queue.add(pRoot);
    boolean leftToRight = true;
    TreeNode left = pRoot, right = pRoot;
    while (!queue.isEmpty()) {
        if (leftToRight) {
            TreeNode p = queue.poll();
            list.add(p.val);
            if (p.left != null) {
                queue.add(p.left);
            }
            if (p.right != null) {
                queue.add(p.right);
            }
            if (p == right) {
                left = queue.peek();
                res.add(list);
                list = new ArrayList<>();
            }
        } else {
            TreeNode p = queue.pollLast();
            list.add(p.val);
            if (p.right != null) {
                queue.addFirst(p.right);
            }
            if (p.left != null) {
                queue.addFirst(p.left);
            }
            if (p == left) {
                right = queue.peekLast();
                res.add(list);
                list = new ArrayList<>();
            }
        }
        leftToRight = !leftToRight;
    }
    return res;
}

서열화 두 갈래 나무

두 함수를 실현하십시오. 각각 서열화와 반서열화 두 갈래 나무에 쓰십시오

서열화와 반서열화 과정이 귀속으로 실현된다면 모든 노드에 대해 StringBuilder를 toString 과정으로 끊임없이 만들어야 한다. 최종적으로 모든 문자열이 단독으로 연결되는 과정이고 이 효율은 매우 낮다.그래서 우리는 대열을 선택하여 실현한다

String Serialize(TreeNode root) {
    if (root == null) {
        return "[]";
    }
    StringBuilder sb = new StringBuilder();
    LinkedList q = new LinkedList<>();
    q.add(root);
    sb.append("[").append(root.val).append(",");
    while (!q.isEmpty()) {
        TreeNode p = q.poll();
        if (p.left != null) {
            sb.append(p.left.val).append(",");
            q.add(p.left);
        } else {
            sb.append("#,");
        }
        if (p.right != null) {
            sb.append(p.right.val).append(",");
            q.add(p.right);
        } else {
            sb.append("#,");
        }
    }
    return sb.deleteCharAt(sb.length() - 1).append("]").toString();
}

TreeNode Deserialize(String str) {
    if (str == null || str.equals("[]")) {
        return null;
    }
    String[] arr = str.substring(1, str.length() - 1).split(",");
    int k = 0, len = arr.length;
    LinkedList q = new LinkedList<>();
    TreeNode root = new TreeNode(Integer.valueOf(arr[k++]));
    q.add(root);
    while (k < len && !q.isEmpty()) {
        TreeNode p = q.poll();
        if (k < len && !"#".equals(arr[k])) {
            p.left = new TreeNode(Integer.valueOf(arr[k]));
            q.add(p.left);
        }
        k++;
        if (k < len && !"#".equals(arr[k])) {
            p.right = new TreeNode(Integer.valueOf(arr[k]));
            q.add(p.right);
        }
        k++;
    }
    return root;
}