二叉树


class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        self.result = 1
        self.dfs(node=root, depth=1)
        return self.result
    
    def dfs(self, node, depth):
        if node is None:
            return
        self.result = max(self.result, depth)

        self.dfs(node.left, depth+1)
        self.dfs(node.right, depth+1)

相关题目：

🏒

104. 二叉树的最大深度

6.信息传递

走到树中的一个节点后

可以自上而下的传递给左节点，右节点（通过传函数参数）

也可以自下而上的传给父节点（通过函数返回值）

涉及深度的题目，既可以自上而下也可以自下而上

6.1自上而下（回溯）

backtracking可以理解为我们想去做一个搜索的操作,类似dfs我们在走一条路不通后我们undo我们的操作，去下一条路再次尝试，在进行的过程中其实我们使用了很多次的recursion 注意这个过程中每条我们尝试的道路是互相不影响的,这也是我们为什么说信息是自上而下传递的，比如subset这道题，找出所有的组合subset，我们的组合是top-down的

对于路径的问题，可以利用栈or队列，在遍历二叉树的时候，顺便把从根节点到当前节点的路径存放的队列 or 栈中。这样每次取出一个节点，顺带也可以取出从根节点到当前节点的路径。此外亦可采用深度优先搜索（回溯算法）进行统计所有路径

信息是从父节点传下来的，所以一般是先序遍历

6.2自下而上

由要解决的problem的定义出发，尝试划分成相同problem的子问题，并且利用子问题的结果来解决原来的问题，而最关键的点有两处：base case和induction rule。 base case代表的是最小号的不可分的问题，这里指的是叶子节点；induction rule表示的是如何利用子问题的结果，表示在当前node处理leftChild，rightChild返回来的结果比如我们在找subtree all nodes sum的时候，我们通过left，right node return back他们的sum，这样我们在每一层的current node节点就可以拿到汇总起来的当前subtree的数据

信息是return回去的，所以一般是后序遍历，当然也有中序遍历，即每一各节点只关注其左子树的信息

💡

Tips:在做这类的题目时，想一下，递归的时候，站在每一个节点上，从该节点向左走，可以拿到左子树的信息回来，向右走可以拿到右子树的信息回来。最后带着左右子树的信息，看你怎么处理。当然，这是后序遍历。如果先带着左子树的信息回来直接处理，处理完才去右子树，那么就是中序遍历。

595 · 二叉树最长连续序列 - LintCode

🎢

614 · 二叉树的最长连续子序列 II - LintCode

《程序员代码面试指南》找二叉树中的最大搜索二叉树 / 找满足二叉搜索条件的最大拓扑结构

7. 树转图

先借助字典将二叉树转为无向图，然后在无向图上进行 DFS 或者 BFS

二叉树转无向图，代码如下：


# 版本1 初始parent为None，child为root
def buildGraph(self, parent, child):
        # 先建立 parent 和 child 的相互映射
        if parent:
            self.graph.setdefault(parent.val,[]).append(child.val)
            self.graph.setdefault(child.val,[]).append(parent.val)
            
        # 再去递归建立子节点
        if child.left:
            self.buildGraph(child, child.left)
        if child.right:
            self.buildGraph(child, child.right)
# 版本2 
def buildGraph(self, root):
        # 先建立 parent 和 child 的相互映射
        if root.left:
            self.graph.setdefault(root.val,[]).append(root.left.val)
            self.graph.setdefault(root.left.val,[]).append(root.val)
            self.buildGraph(root.left)
        if root.right:
            self.graph.setdefault(root.val,[]).append(root.right.val)
            self.graph.setdefault(root.right.val,[]).append(root.val)
            self.buildGraph(root.right)