leetcode107-python 두 갈래 트리 차원 두루 훑어보기

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
For example:Given binary tree  [3,9,20,null,null,15,7] ,

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

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

문제 해결 요점:
1. 두 갈래 트리를 층층이 훑어보지만 노드를 결과의list에 직접 넣지 않고 노드의 수치를list에 넣어야 원하는 것을 얻을 수 있다.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrderBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if root == None:
            return []
        st = []
        st.append(root)
        k = []
        k.append(root.val)
        ans = []
        ans.insert(0, k)
        p = st[0]
        while len(st) != 0:
            temp = st[0]
            if temp.left != None:
                st.append(temp.left)
            if temp.right != None:
                st.append(temp.right)

            if p == st[0]:
                p = st[len(st)-1]
                if p != st[0]:
                    k = []
                    for i in range(1, len(st)):
                        k.append(st[i].val)
                    ans.insert(0, k)
                    
            st.pop(0)
        return ans

참고 사항:
1.dfs의 과정은 대기열에서 앞의 요소가 하나씩 튀어나오는 것이 아니라 다음 층의 목록과 직접 일치하는 것을 반복한다.
2.l1=l1+[l2]의 문법은 l2를 원소로 l1에 넣을 수 있으며, l1=[l2]+l1이라면 l2는 l1의 앞에 넣는다

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrderBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if root == None:
            return []
        queue = []
        queue.append(root)
        ans = []

        while queue:
            nodes = []
            no_val = []

            for i in queue:
                if i.left != None:
                    nodes.append(i.left)
                if i.right != None:
                    nodes.append(i.right)
                no_val += [i.val]
            queue = nodes
            ans = [no_val] + ans
        return ans