題目

題目連結
目標函式 : isBalanced(root)
- Input : root: TreeNode
- Output : bool

解題概念

題意 : 使用兩個 Stack 去實作 Queue的功能，須包含 :
1. push(x) : 將 x 加入 Queue 尾端
2. pop() : 刪除 Queue 最前端的元素並回傳
3. peek() : 回傳 Queue 最前端的元素 (不須刪除)
4. empty() : 回傳 Queue 是否為空

我的寫法

想法 : 此題在 Stack 與 Queue 範疇中也是經典的一題應用題，實作如下 :
1. 宣告兩個 Stack s 與 t
2. 實作四種功能 :
  - push(x) : 將元素 Push 到 Stack s 中即可
  - peek() : 確認 Stack t 是否為空 :
    - 若 t 為空且 s 不為空，則對 t 一一執行 pop()，並依序 Push 到 t 中
    - 若 t 為空且 s 也為空，代表 Queue 沒東西
    - 否則直接對 t 執行 pop() 即可
  - pop() : 先確認 t 是否可以進行 pop()，否則取出 s 的第一個元素
  - empty() : 若 t 為空且 s 也為空，代表 Queue 為空

程式碼 :

class MyQueue(object):

s = None
t = None

def __init__(self):
    self.s = list()
    self.t = list()

def push(self, x):
    """
    :type x: int
    :rtype: None
    """
    self.s.append(x)
    

def pop(self):
    """
    :rtype: int
    """
    if len(self.t) == 0:
        while len(self.s) != 0:
            self.t.append(self.s.pop())
    return self.t.pop()

def peek(self):
    """
    :rtype: int
    """
    if len(self.t) != 0:
        return self.t[len(self.t) - 1]
    else:
        return self.s[0]

def empty(self):
    """
    :rtype: bool
    """
    if len(self.s) == 0 and len(self.t) == 0:
        return True
    return False

成效 :
- Time Complexity : $\color{DB4D6D}{O(1)}$ or $\color{DB4D6D}{O(n)}$
- Runtime: 15 ms (faster than 71.10%)
- Memory Usage: 13.3 MB (more than 69.11%)

解答 or 其他優秀寫法

想法 : 把我的寫法修得更加乾淨
- push(x) : 將元素 Push 到 Stack s 中即可
- pop() : 先執行 peek()，確認 Queue 有元素，同時把所有元素都移到 Stack t 中，再取出 s 的第一個元素
- peek() : 確認 Stack t 是否為空 :
  - 若 t 為空，則對 t 一一執行 pop()，並依序 Push 到 t 中
  - 再回傳 t 尾端的元素
- empty() : 若 t 為空且 s 也為空，代表 Queue 為空

程式碼 :

class MyQueue(object):

s = None
t = None

def __init__(self):
    self.s = list()
    self.t = list()

def push(self, x):
    """
    :type x: int
    :rtype: None
    """
    self.s.append(x)
    

def pop(self):
    """
    :rtype: int
    """
    self.peek()
    return self.t.pop()

def peek(self):
    """
    :rtype: int
    """
    if not self.t:
        while self.s:
            self.t.append(self.s.pop())
    return self.t[-1]

def empty(self):
    """
    :rtype: bool
    """
    return not self.s  and not self.t

成效 :
- Time Complexity : $\color{DB4D6D}{O(1)}$ or $\color{DB4D6D}{O(n)}$
- Runtime: 13 ms (faster than 81.29%)
- Memory Usage: 13.4 MB (more than 69.11%)