題目介紹

描述：

請(qǐng)考慮一顆二叉樹(shù)上所有的葉子，這些葉子的值按從左到右的順序排列形成一個(gè) 葉值序列 。

舉個(gè)例子，如上圖所示，給定一顆葉值序列為 (6, 7, 4, 9, 8) 的樹(shù)。

如果有兩顆二叉樹(shù)的葉值序列是相同，那么我們就認(rèn)為它們是 葉相似 的。

如果給定的兩個(gè)頭結(jié)點(diǎn)分別為 root1 和 root2 的樹(shù)是葉相似的，則返回 true；否則返回 false 。

提示：

給定的兩顆樹(shù)可能會(huì)有 1 到 200 個(gè)結(jié)點(diǎn)。 給定的兩顆樹(shù)上的值介于 0 到 200 之間。

解題思路：

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

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

二叉樹(shù)題目的一個(gè)難點(diǎn)在于如何通過(guò)題目的要求思考出每一個(gè)節(jié)點(diǎn)需要做什么

二叉樹(shù)解題策略

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

三種基本的遍歷方式，都可以用遞歸來(lái)實(shí)現(xiàn)。寫(xiě)遞歸算法的時(shí)候，需要注意遞歸退出條件以及遞歸操作的表達(dá)。

得到兩棵樹(shù)的葉值序列，然后比較是否相等

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

def leafSimilar4(self, root1, root2):
        def dfs(node, res):
            if not node: return     # 如果根節(jié)點(diǎn)為空就結(jié)束這個(gè)
            if not node.left and not node.right:
                # 如果沒(méi)有左右孩子就把它加進(jìn)去
                res += [node.val]
            else:    # 有左孩子或者右孩子就遍歷
                dfs(node.left, res)
                dfs(node.right, res)
            return res
        num1 = []
        num2 = []
        return dfs(root1, num1) == dfs(root2, num2)

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

解法一

方法：深度優(yōu)先搜索 首先，讓我們找出給定的兩個(gè)樹(shù)的葉值序列。之后，我們可以比較它們，看看它們是否相等。

要找出樹(shù)的葉值序列，我們可以使用深度優(yōu)先搜索。如果結(jié)點(diǎn)是葉子，那么 dfs 函數(shù)會(huì)寫(xiě)入結(jié)點(diǎn)的值，然后遞歸地探索每個(gè)子結(jié)點(diǎn)。這可以保證按從左到右的順序訪問(wèn)每片葉子，因?yàn)樵谟液⒆咏Y(jié)點(diǎn)之前完全探索了左孩子結(jié)點(diǎn)。

def leafSimilar(self, root1, root2):
        def dfs(node):
            if node:
                if not node.left and not node.right:
                    yield node.val
                yield from dfs(node.left)
                yield from dfs(node.right)
        return list(dfs(root1)) == list(dfs(root2))

解法二

定義先序遍歷函數(shù)，返回葉值序列。并判斷兩個(gè)數(shù)root1和root2返回的葉值序列是否相同。

def leafSimilar2(self, root1, root2):
        def preorder(node, leaf_list):
            if not node: return None
            if not node.left and not node.right:
                leaf_list.append(node.val)
            preorder(node.left, leaf_list)
            preorder(node.right, leaf_list)
            return leaf_list
        return preorder(root1, []) == preorder(root2, [])

解法三

遞歸方法

def leafSimilar3(self, root1, root2):
        num1 = []
        num2 = []
        def getleaves(node, nums):
            if node and (not node.left and not node.right):
                nums.append(node.val)
            if node.left:
                getleaves(node.left, nums)
            if node.right:
                getleaves(node.right, nums)
            return nums
        return getleaves(root1, num1) == getleaves(root2, num2)

相關(guān)知識(shí)總結(jié)和思考

相關(guān)知識(shí)：

BFS：廣度/寬度優(yōu)先。其實(shí)就是從上到下，先把每一層遍歷完之后再遍歷一下一層。

可以使用Queue的數(shù)據(jù)結(jié)構(gòu)。我們將root節(jié)點(diǎn)初始化進(jìn)隊(duì)列，通過(guò)消耗尾部，插入頭部的方式來(lái)完成BFS。

二叉搜索樹(shù)（BST）的特性：

1. 若它的左子樹(shù)不為空，則所有左子樹(shù)上的值均小于其根節(jié)點(diǎn)的值
2. 若它的右子樹(shù)不為空，則所有右子樹(shù)上的值均大于其根節(jié)點(diǎn)的值
3. 它的左右子樹(shù)也分別為二叉搜索樹(shù)

遞歸與迭代的區(qū)別

遞歸：重復(fù)調(diào)用函數(shù)自身實(shí)現(xiàn)循環(huán)稱(chēng)為遞歸； 迭代：利用變量的原值推出新值稱(chēng)為迭代，或者說(shuō)迭代是函數(shù)內(nèi)某段代碼實(shí)現(xiàn)循環(huán)；