首先定义一个节点类，包含三个成员变量，分别是节点值，左指针，右指针，如下代码所示：
class Node(object): def __init__(self, value): self.value = value self.left = None self.right = None
接下来就是二叉树的相关工作：
1)初始化一棵二叉树
class Solution(object): def __init__(self): root = Node(6) B = Node(4) root.left = B C = Node(7) root.right = C D = Node(1) B.left = D E = Node(2) B.right = E F = Node(3) C.left = F G = Node(5) C.right = G H = Node(6) I = Node(8) D.left = H E.left = I self.root = root self.max_value = 0 self.path = []
2) 求二叉树的深度(高度)
def max_depth(self,root): if root == None: return 0 if (root.left != None) & (root.right != None): return max(1 + self.max_depth(root.left), 1 + self.max_depth(root.right)) elif (root.left != None) & (root.right == None): return 1 + self.max_depth(root.left) elif (root.left == None) & (root.right != None): return 1 + self.max_depth(root.right) else: return 1
3）求根节点到叶子节点的最大路径值
def max_sum(self, root, Sum): if root == None: return self.max_value if (root.left != None) & (root.right != None): self.max_sum(root.left, Sum + root.value) self.max_sum(root.right, Sum + root.value) elif (root.left != None) & (root.right == None): self.max_sum(root.left, Sum + root.value) elif (root.left == None) & (root.right != None): self.max_sum(root.right, Sum + root.value) else: if (Sum + root.value) > self.max_value: self.max_value = Sum + root.value
4）求根节点到叶子节点的最大路径值对应的路径
def FindPath(self, root, expectNumber): ans = [] # 所有路径的集合 if root == None: return ans def iterpath(root, expectNumber, dir=[]): if expectNumber > root.value: dir.append(root.value) # dir保存当前路径（不一定是符合要求的路径） # 分别在左右子树中寻找并更新期望值 if root.left != None: iterpath(root.left, expectNumber - root.value, dir) if root.right != None: iterpath(root.right, expectNumber - root.value, dir) elif expectNumber == root.value: dir.append(root.value) if root.right == None and root.left == None: # 如果节点的值与期望值相同，则判断节点是否为叶子结点，如果是叶子结点则是符合条件的路径 tmp = dir[:] ans.append(tmp) else: dir.append(0) dir.pop() # ！！！！！！！！！！！！！ iterpath(root, expectNumber) return ans
求二叉树的深度，从根节点到叶子节点的最大值，以及最大路径的完整代码如下：
class Node(object): def __init__(self, value): self.value = value self.left = None self.right = None class Solution(object): def __init__(self): root = Node(6) B = Node(4) root.left = B C = Node(7) root.right = C D = Node(1) B.left = D E = Node(2) B.right = E F = Node(3) C.left = F G = Node(5) C.right = G H = Node(6) I = Node(8) D.left = H E.left = I self.root = root self.max_value = 0 self.path = [] def max_depth(self,root): if root == None: return 0 if (root.left != None) & (root.right != None): return max(1 + self.max_depth(root.left), 1 + self.max_depth(root.right)) elif (root.left != None) & (root.right == None): return 1 + self.max_depth(root.left) elif (root.left == None) & (root.right != None): return 1 + self.max_depth(root.right) else: return 1 def max_sum(self, root, Sum): if root == None: return self.max_value if (root.left != None) & (root.right != None): self.max_sum(root.left, Sum + root.value) self.max_sum(root.right, Sum + root.value) elif (root.left != None) & (root.right == None): self.max_sum(root.left, Sum + root.value) elif (root.left == None) & (root.right != None): self.max_sum(root.right, Sum + root.value) else: if (Sum + root.value) > self.max_value: self.max_value = Sum + root.value def FindPath(self, root, expectNumber): ans = [] # 所有路径的集合 if root == None: return ans def iterpath(root, expectNumber, dir=[]): if expectNumber > root.value: dir.append(root.value) # dir保存当前路径（不一定是符合要求的路径） # 分别在左右子树中寻找并更新期望值 if root.left != None: iterpath(root.left, expectNumber - root.value, dir) if root.right != None: iterpath(root.right, expectNumber - root.value, dir) elif expectNumber == root.value: dir.append(root.value) if root.right == None and root.left == None: # 如果节点的值与期望值相同，则判断节点是否为叶子结点，如果是叶子结点则是符合条件的路径 tmp = dir[:] ans.append(tmp) else: dir.append(0) dir.pop() # ！！！！！！！！！！！！！ iterpath(root, expectNumber) return ans if __name__ == ‘__main__‘: binary_tree = Solution() max_depth = binary_tree.max_depth(binary_tree.root) binary_tree.max_sum(binary_tree.root, 0) path = binary_tree.FindPath(binary_tree.root, binary_tree.max_value) print("二叉树的最大深度(高度)", max_depth) print("从根节点到叶子节点的路径和最大值", binary_tree.max_value) print("从根节点到叶子节点的最大路径", path)
求二叉树的深度，从根节点到叶子节点的最大值，以及最大路径(python代码实现)
原文：https://www.cnblogs.com/shnuxiaoan/p/12131926.html