LeetCode0993: 二叉樹的堂兄弟節(jié)點

題目介紹

描述：

在二叉樹中匣距，根節(jié)點位于深度 0 處，每個深度為 k 的節(jié)點的子節(jié)點位于深度 k+1 處上荡。

如果二叉樹的兩個節(jié)點深度相同趴樱，但父節(jié)點不同，則它們是一對堂兄弟節(jié)點酪捡。

我們給出了具有唯一值的二叉樹的根節(jié)點 root叁征，以及樹中兩個不同節(jié)點的值 x 和 y。

只有與值 x 和 y 對應(yīng)的節(jié)點是堂兄弟節(jié)點時逛薇，才返回 true捺疼。否則，返回 false永罚。

解題思路：

遞歸算法的關(guān)鍵是要明確函數(shù)的「定義」是什么啤呼，然后相信這個定義，利用這個定義推導(dǎo)最終結(jié)果呢袱。

寫樹相關(guān)的算法官扣，簡單說就是，先搞清楚當(dāng)前 root 節(jié)點該做什么羞福，然后根據(jù)函數(shù)定義遞歸調(diào)用子節(jié)點惕蹄，遞歸調(diào)用會讓孩子節(jié)點做相同的事情。

二叉樹題目的一個難點在于如何通過題目的要求思考出每一個節(jié)點需要做什么

二叉樹解題策略

一遞歸二隊列 + 迭代（層次遍歷）三棧 + 迭代（非遞歸遍歷）四其它

三種基本的遍歷方式治专，都可以用遞歸來實現(xiàn)卖陵。寫遞歸算法的時候，需要注意遞歸退出條件以及遞歸操作的表達张峰。

自己的解法實現(xiàn)

def isCousins4(self, root, x, y):
        if not root: return []
        stack = [root]
        while stack:
            counter = 0
            for _ in range(len(stack)):
                node = stack.pop(0)
                if node.left and node.right and ((node.left.val == x and node.right.val == y) or (node.left.val == x and node.right.val == y)):
                    return False
                if node.val == x or node.val == y:
                    counter += 1
                    if counter == 2:
                        return True
                if node.left:
                    stack.append(node.left)
                if node.right:
                    stack.append(node.right)

網(wǎng)上比較優(yōu)秀的解法

解法一

方法：標(biāo)記父節(jié)點與深度思路當(dāng)且僅當(dāng)一對節(jié)點深度相同而父節(jié)點不相同時泪蔫，它們是堂兄弟節(jié)點。一種非常直接的方法就是通過某種方法求出每一個節(jié)點的深度與父節(jié)點挟炬。

算法我們用深度優(yōu)先搜索標(biāo)記每一個節(jié)點鸥滨，對于每一個節(jié)點 node嗦哆，它的父親為 par，深度為 d婿滓，我們將其記錄到 Hashmap 中：parent[node.val] = par 且 depth[node.val] = d老速。

def isCousins(self, root, x, y):
        parent = {}
        depth = {}
        def dfs(node, par = None):
            if node:
                depth[node.val] = 1 + depth[par.val] if par else 0
                parent[node.val] = par
                dfs(node.left, node)
                dfs(node.right, node)
        dfs(root)
        return depth[x] == depth[y] and parent[x] != parent[y]

解法二

方法1——深度優(yōu)先搜索輸出x和y的深度以及它們的父結(jié)點，然后按照題意比較即可

def __init__(self):
        self.d = 0
        self.node = TreeNode()

    def isCousins2(self, root, x, y):
        def dfs(node, num, tmp):
            if not node: return
            tmp += 1
            if (node.left and node.left.val == num) or (node.right and node.right.val == num):
                self.d = tmp + 1
                self.node = node
                return
            dfs(node.left, num, tmp)
            dfs(node.right, num, tmp)
        dfs(root, x, 0)
        dx, xf = self.d, self.node

        dfs(root, y, 0)
        dy, yf = self.d, self.node

        if dx == dy and xf.val != yf.val:
            return True
        return False

解法三

哈希+BFS

def isCousins3(self, root, x, y):
        queue, hm = [(root, None)], {}  # BFS, 每層掃描完后考察是否找到其中一個點(若找到則跳出)
        while queue and not (x in hm or y in hm):
            n = len(queue)
            for i in range(n):  # 掃描每一層
                node, parent = queue.pop(0)
                if node:  # 把當(dāng)前節(jié)點作為父節(jié)點信息往下傳
                    queue += [(node.left, node), (node.right, node)]
                    hm[node.val] = parent  # 直接哈希記錄父節(jié)點
        return (x in hm and y in hm) and hm[x] != hm[y]  # 同一層且父節(jié)點不同