題目介紹

描述：

給定一個(gè)根為 root 的二叉樹，每個(gè)結(jié)點(diǎn)的深度是它到根的最短距離。

如果一個(gè)結(jié)點(diǎn)在整個(gè)樹的任意結(jié)點(diǎn)之間具有最大的深度，則該結(jié)點(diǎn)是最深的。

一個(gè)結(jié)點(diǎn)的子樹是該結(jié)點(diǎn)加上它的所有后代的集合。

返回能滿足“以該結(jié)點(diǎn)為根的子樹中包含所有最深的結(jié)點(diǎn)”這一條件的具有最大深度的結(jié)點(diǎn)。

解題思路：

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

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

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

二叉樹解題策略

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

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

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

def subtreeWithAllDeepest4(self, root):
        def dfs(node):
            if not node:
                return None, 0
            left, i = dfs(node.left)
            right, j = dfs(node.right)
            if i > j:
                return left, i + 1
            elif j > i:
                return right, j + 1
            return node, i + 1

        return dfs(root)[0]

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

解法一

方法一： 兩次深度優(yōu)先搜索 思路 最直白的做法，先做一次深度優(yōu)先搜索標(biāo)記所有節(jié)點(diǎn)的深度來找到最深的節(jié)點(diǎn)，再做一次深度優(yōu)先搜索用回溯法找最小子樹。定義第二次深度優(yōu)先搜索方法為 answer(node)，每次遞歸有以下四種情況需要處理：

1. 如果 node 沒有左右子樹，返回 node。
2. 如果 node 左右子樹的后代中都有最深節(jié)點(diǎn)，返回 node。
3. 如果只有左子樹或右子樹中有且擁有所有的最深節(jié)點(diǎn)，返回這棵子樹的根節(jié)點(diǎn)（即 node 的左/右孩子）。
4. 否則，當(dāng)前子樹中不存在答案。

算法 先做一次深度優(yōu)先搜索標(biāo)記所有節(jié)點(diǎn)的深度，再做一次深度優(yōu)先搜索找到最終答案。

def subtreeWithAllDeepest(self, root):
        # Tag each node with it's depth.
        depth = {None: -1}
        def dfs(node, parent = None):
            if node:
                depth[node] = depth[parent] + 1
                dfs(node.left, node)
                dfs(node.right, node)
        dfs(root)

        max_depth = max(depth.itervalues())

        def answer(node):
            # Return the answer for the subtree at node.
            if not node or depth.get(node, None) == max_depth:
                return node
            L, R = answer(node.left), answer(node.right)
            return node if L and R else L or R
        return answer(root)

解法二

方法二： 一次深度優(yōu)先搜索 思路 可以把 方法一 中兩次深度優(yōu)先搜索合并成一次，定義方法 dfs(node)，與方法一中不同的是 dfs(node) 返回兩個(gè)值，子樹中的答案和 node 節(jié)點(diǎn)到最深節(jié)點(diǎn)的距離。

算法 dfs(node) 返回的結(jié)果有兩個(gè)部分：

1. Result.node：包含所有最深節(jié)點(diǎn)的最小子樹的根節(jié)點(diǎn)。
2. Result.dist：node 到最深節(jié)點(diǎn)的距離。 分別計(jì)算 dfs(node) 的兩個(gè)返回結(jié)果：

對于 Result.node： 如果只有一個(gè) childResult 具有最深節(jié)點(diǎn)，返回 childResult.node。

如果兩個(gè)孩子都有最深節(jié)點(diǎn)，返回 node。

Result.dist 為 childResult.dist 加 1。

def subtreeWithAllDeepest2(self, root):
        import collections
        Result = collections.namedtuple("Result", ("node", "dist"))
        def dfs(node):
            if not node: return Result(None, 0)
            L, R = dfs(node.left), dfs(node.right)
            if L.dist > R.dist:
                return Result(L.node, L.dist + 1)
            if L.dist < R.dist:
                return Result(R.node, R.dist + 1)
            return Result(node, L.dist + 1)
        return dfs(root).node

解法三

利用遞歸的思想。首先，要明確只有當(dāng)左子樹和右子樹的深度相同時(shí)，我們才返回以當(dāng)前結(jié)點(diǎn)為根的子樹！，否則遞歸深度更深的左右子樹。

def depth(self, tree): #    計(jì)算樹的深度
        if tree == None:
            return 1
        return max(self.depth(tree.left), self.depth(tree.right)) + 1
    def subtreeWithAllDeepest3(self, root):
        left_depth = self.depth(root.left)
        rigth_depth = self.depth(root.right)
        if left_depth == rigth_depth:
            return root
        else:
            return self.subtreeWithAllDeepest(root.left) if left_depth > rigth_depth else self.subtreeWithAllDeepest(root.right)

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

相關(guān)知識：

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

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

二叉搜索樹（BST）的特性：

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

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

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