超瑣碎 ≈ 完整記錄 + 深入探究 + 任性吐槽
問題地址蟋字，難度：Easy辑奈，標(biāo)簽：Tree
若有錯(cuò)誤之處請予以指正:)
問題描述
A binary tree is univalued if every node in the tree has the same value.
Return true if and only if the given tree is univalued.
Example 1:
Input: [1,1,1,1,1,null,1]
Output: true
Example 2:
Input: [2,2,2,5,2]
Output: false
Note:
- The number of nodes in the given tree will be in the range
[1, 100]. - Each node's value will be an integer in the range
[0, 99].
題意分析
這道題需要了解二叉搜索樹的定義啥繁，以及遞歸/循環(huán)的知識月弛。解決的思路：第一種是遞歸的每一步只看一對父子的值是否相等鸥咖，然后傳遞下去符喝，如果每一對都等，肯定全等婿滓；第二種是遞歸只管把所有節(jié)點(diǎn)值取出來老速，最后看一下是不是全等；第三種是先獲取root的值凸主，再遞歸搜索root的子樹看是不是所有節(jié)點(diǎn)都等于這個(gè)值橘券。
實(shí)現(xiàn)方法（及調(diào)優(yōu)過程）
以下前兩種方法對應(yīng)LeetCode上的Solution，第三種是上面沒有的卿吐。
方法1：60 ms
方法1對應(yīng)第一種思路旁舰，看起來挺容易，但做起來有點(diǎn)繞嗡官。
isUnivalTree(root)的結(jié)果即是“root所代表的子樹是否為全等”這個(gè)命題的真值箭窜。首先須確定root到底有沒有左子樹和右子樹，如果沒有衍腥，則真值為True绽快；如果有芥丧，則root的值與左右兩個(gè)子節(jié)點(diǎn)的值必須相等，且兩個(gè)子節(jié)點(diǎn)所代表的子樹也必須是全等的坊罢，兩個(gè)條件同時(shí)滿足時(shí)真值為True。
下面貼的代碼是我參考了Solution以后改的擅耽，原來的代碼非常簡潔（幾乎就是邏輯運(yùn)算式）活孩，我只是把邏輯運(yùn)算的順序改得清楚了點(diǎn)。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isUnivalTree(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
left = (not root.left) or ((root.val == root.left.val) and self.isUnivalTree(root.left))
right = (not root.right) or ((root.val == root.right.val) and self.isUnivalTree(root.right))
return left and right
- 時(shí)間復(fù)雜度：O(n) （
n為樹的節(jié)點(diǎn)數(shù)乖仇，最壞情況下每個(gè)節(jié)點(diǎn)都被遍歷） - 空間復(fù)雜度：O(m) （遞歸本身的棧會占用一些資源憾儒，
m為樹的深度，影響棧的數(shù)量）
方法2：36 ms
方法2對應(yīng)第二種思路乃沙，個(gè)人感覺不夠優(yōu)雅起趾，因?yàn)楸闅v完樹以后還沒有得到最后的答案（真值）。但實(shí)現(xiàn)起來容易多了警儒。這里我直接貼了LeetCode上的Solution代碼训裆，其組織形式值得理解：values放在isUnivalTree里，isUnivalTree內(nèi)部再寫一個(gè)用于遞歸的函數(shù)getValues蜀铲，這樣values的作用域剛好使得getValues少一個(gè)丑陋的參數(shù)边琉。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isUnivalTree(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
values = []
def getValues(node):
if node:
values.append(node.val)
getValues(node.left)
getValues(node.right)
getValues(root)
return len(set(values)) == 1
- 時(shí)間復(fù)雜度：O(n) （
n為樹的節(jié)點(diǎn)數(shù)，最壞情況下每個(gè)節(jié)點(diǎn)都被遍歷） - 空間復(fù)雜度：O(m) （遞歸本身的棧會占用一些資源记劝，
m為樹的深度变姨，影響棧的數(shù)量）
方法3：70 ms
方法3的實(shí)現(xiàn)從組織方式上參考了方法2，而遞歸輸出了真值則更像方法1厌丑，代碼里比較tricky的地方是如果當(dāng)前節(jié)點(diǎn)為None時(shí)定欧，會返回True（方法1里其實(shí)也有這樣的邏輯）。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isUnivalTree(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
root_val = root.val
def hasUniValue(node):
if node:
return node.val == root_val and hasUniValue(node.left) and hasUniValue(node.right)
else:
return True
return hasUniValue(root)
弄清上面的邏輯后怒竿，還可仿照方法1改寫hasUniValue砍鸠，省略if語句。
def hasUniValue(node):
return not node or (node.val == root_val and hasUniValue(node.left) and hasUniValue(node.right))
- 時(shí)間復(fù)雜度：O(n) （
n為樹的節(jié)點(diǎn)數(shù)愧口，最壞情況下每個(gè)節(jié)點(diǎn)都被遍歷） - 空間復(fù)雜度：O(m) （遞歸本身的棧會占用一些資源睦番，
m為樹的深度，影響棧的數(shù)量）
