LeetCode 노트-107 두 갈래 트리 레이아웃 II

제목:
두 갈래 나무를 정해서 노드 값이 밑에서 위로 올라가는 차원을 되돌려줍니다.(즉, 잎 노드가 있는 층에서 뿌리 노드가 있는 층으로 한 층씩 왼쪽에서 오른쪽으로 옮겨간다)
예를 들어 두 갈래 나무를 지정합니다[3,9,20,null,null,15,7] ,

    3
   / \
  9  20
    /  \
   15   7

아래에서 위로 올라가는 단계를 다음과 같이 되돌려줍니다.

[
  [15,7],
  [9,20],
  [3]
]

집합에 있어서는 아직 어리둥절하다...직접 인터넷에서 대신들의 사고방식과 코드를 찾았다.
사고방식 1: 전체적인 사고방식은 나무의 모든 층을 집합 링크드 리스트에 저장하고addFirst 순서로 각 층을 추가하면 아래에서 위로 단계를 반복할 수 있다.다음 코드에서result는 마지막 결과 숫자를 저장하고queue는 모든 줄의 노드를 저장하고sin은 모든 줄의 노드 값을 저장합니다.노드를queue에 한 번에 추가합니다. 대기열이 비어 있지 않을 때 대기열의 노드를 꺼내서 그 값을sin에 넣고 이 노드의 좌우 노드가 비어 있는지, 비어 있지 않을 때 대기열에 추가합니다.한 층을 처리한 후, 모든 줄의sin을result에 추가합니다.
나 자신은 이 사고방식에 따라 글을 쓸 수 없다. 주로 각 줄의 요소를 어떻게 확정하는지에 달려 있다. 그리고queue의 창설과 일부 조작에 대해 익숙하지 않다.
코드:
/**  * Definition for a binary tree node.  * public class TreeNode {  *     int val;  *     TreeNode left;  *     TreeNode right;  *     TreeNode(int x) { val = x; } *} */class Solution {public List > levelorderBottom(TreeNode root) {/result는 마지막 결과 숫자를 저장하는 데 사용됩니다. linkedList를 사용하십시오. integerLinkedList > result = New LinkedList > (), if (root==null) return result;/queue는 각 줄의 노드를 저장하는 데 사용되며, TreeNode Queue queue = New LinkedList ();         queue.add(root);//줄마다 노드 개수 int i=queue.size();         TreeNode tem=null;//각 행의 노드를 저장하는 값 List sin=New ArrayList<>();//한 줄의 노드가 비어 있지 않음 while (!queue.isEmpty ()) {if (i==0) {//한 줄의 데이터를 다 처리하고/addFirst를 주의하십시오. 항상 머리 result.addFirst (sin), i=queue.size ();sin=new ArrayList<> ();            }             --i;//줄마다 노드tem=queue를 꺼냅니다.poll();             sin.add(tem.val);                          if(tem.left!=null)             {queue.add(tem.left);}             if(tem.right!=null)             {queue.add(tem.right);}                      }                   result.addFirst(sin);         return result;     } }
사고방식2: 이것은 인터넷에서 신이 밀어내는 알고리즘입니다.여기서 가장 중요한 것은 각 층의 번호를 아는 것이다.노드가 왼쪽에서 오른쪽으로 순서대로 함수를 호출합니다.각 노드가 비어 있는지 아닌지를 먼저 판단하고 비어 있지 않으면 결과result에 ArrayList를 추가한 다음에 해당하는 층호 가산값을 계산하여 가입합니다.마지막으로 현재 노드의 좌우 노드에 대해 공백이 될 때까지 함수를 호출합니다.

public List> levelOrderBottom2(TreeNode root) {
        LinkedList> result = new LinkedList>();

        levelRecursion(root, result, 0);

        return result;
    }

    /**
     *  
     */
    private void levelRecursion(TreeNode node,
            LinkedList> result, int level) {
        if (node == null) {
            return;
        }
        if (result.size() < level + 1) {//  
            result.addFirst(new ArrayList());
        }
        result.get(result.size() - 1 - level).add(node.val);

        levelRecursion(node.left, result, level + 1);
        levelRecursion(node.right, result, level + 1);
    }

 
실행 시 가장 빠른 범례: 상기 사고방식과 기본적으로 일치

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List> levelOrderBottom(TreeNode root) {
        LinkedList> l = new LinkedList();
        if (root == null) return l;
        Queue q = new LinkedList();
        Stack> s = new Stack();
        q.offer(root);
        int i = q.size();
        List list = new LinkedList();
        TreeNode p = null;
        while(q.size() > 0) {
            if (i == 0) {
                l.addFirst(list);
                i = q.size();
                list = new LinkedList();
            }

            p = q.poll();
            list.add(p.val);
            
            --i;
            
            if (p.left != null) q.offer(p.left);
            if (p.right != null) q.offer(p.right);
            
        }
        
        l.addFirst(list);
            
        return l;
    }
}