数据结构|树的概念及其应用（Python）二叉树|数据结构|力扣|python

树的概念及其应用（Python）

- 1. 树
- 2. 二叉树
- - 1.1 二叉树的前序遍历
  - 1.2 二叉树的中序遍历
  - 1.3 二叉树的后序遍历
  - 1.4 二叉树的应用
  - - 104. 二叉树的最大深度。
    - 543. 二叉树的直径。

1. 树 【数据结构|树的概念及其应用（Python）】树是一种由节点（node）和边（edges）构成层级关系的结构。
如果你了解 linux 文件结构（tree 命令），它的结构也是一棵树。
我们快速看下树涉及到的一些概念：

文章图片

根节点(root): 树的最上层的节点，任何非空的树都有一个节点
路径(path): 从起始节点到终止节点经历过的边
父亲(parent)：除了根节点，每个节点的上一层边连接的节点就是它的父亲(节点)
孩子(children): 每个节点由边指向的下一层节点
兄弟(siblings): 同一个父亲并且处在同一层的节点
子树(subtree): 每个节点包含它所有的后代组成的子树
叶子节点(leaf node): 没有孩子的节点成为叶子节点

2. 二叉树二叉树是树结构里面最常用的一种树结构，其实二叉树就是一种简单的树。
二叉树的每个节点最多包含两个孩子。

文章图片

文章图片

从上边的图来看几个二叉树的概念：

节点深度(depth): 节点对应的 level 数字。
树的高度(height): 二叉树的高度就是 level 数 + 1，因为 level 从 0开始计算的。
树的宽度(width): 二叉树的宽度指的是包含最多节点的层级的节点数。
树的 size：二叉树的节点总个数。

一棵 size 为 n 的二叉树高度最多可以是 n，最小的高度是 ?lgn?+1，这里 log 以 2 为底简写为 lgn。
1.1 二叉树的前序遍历
一棵二叉树的前序遍历结果 = 根节点 + 左子树的前序遍历结果 + 右子树的前序遍历结果。
可以理解为有序的遍历二叉树。

class Solution: def preorderTraversal(self, root:TreeNode) -> List[int]: self.res = [] self.traverse(root) #从 root 开始遍历 return self.res # 返回的是 listdef traverse(self, root: TreeNode): if root == None: returnself.res.append(root.val) # 前序遍历位置 self.traverse(root.left) self.traverse(root.right)

1.2 二叉树的中序遍历
二叉树的中序遍历，一般在二叉搜索树（BST）中最为常用。
你完全可以把 BST 的中序遍历认为是遍历有序数组。

class Solution: def inorderTraversal(self, root: TreeNode) -> List[int]: self.res = [] self.traverse(root) return self.resdef traverse(self, root: TreeNode): if root == None: returnself.traverse(root.left) self.res.append(root.val) #中序遍历位置 self.traverse(root.right)

1.3 二叉树的后序遍历
后序遍历通过递归的返回，返回了二叉树子节点的信息。

class Solution: def postorderTraversal(self, root: TreeNode) -> List[int]: self.res = [] self.traverse(root) return self.resdef traverse(self, root: TreeNode): if root == None: returnself.traverse(root.left) self.traverse(root.right) self.res.append(root.val) #后续遍历位置

1.4 二叉树的应用
对于二叉树的遍历，前序遍历执行是自顶向下的，而后序遍历执行是自底向上的。
以上三种遍历过程是通过递归来实现的，也是 DFS 在二叉树中的应用。
在应用中，二叉树的递归方法使用可以分两类思路：

第一类是直接遍历一遍二叉树，对应前序遍历。
第二类是分解问题，变为通过子问题求解，对应后序遍历。

遇到问题是否可以通过遍历一遍二叉树得到答案**（前序遍历）**？
如果不能的话，是否可以通过分解问题，用子问题（子树）的答案推导出原问题的答案**（后序遍历）**。
用几个例子来看一下：
104. 二叉树的最大深度。

文章图片

求二叉树的最大深度，也就是求这棵树的左右子树深度最大的值，直接遍历二叉树就能解决此问题。

# Definition for a binary tree node. # class TreeNode: #def __init__(self, val=0, left=None, right=None): #self.val = val #self.left = left #self.right = right class Solution: def maxDepth(self, root: Optional[TreeNode]) -> int: return self.traverse(root)def traverse(self, root): if not root: return 0 return max(self.traverse(root.left), self.traverse(root.right)) + 1 # 递归，左右子树的最大深度 # 加 1 是加上根节点的深度。

543. 二叉树的直径。

文章图片

根据题目，直径可以理解为任意节点的左右子树的最大深度之和。
那么直接的想法是对每个节点计算左右子树的最大高度，得出每个节点的直径，从而得出最大的那个直径。
解决这题的关键在于，每一条二叉树的直径长度，就是一个节点的左右子树的最大深度之和。
这就是把原问题分解为子问题的方法。

class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int: self.max = 0 self.traverse(root) return self.maxdef traverse(self, root): if not root: return 0 l = self.traverse(root.left) #求该节点左子树的深度 r = self.traverse(root.right)#求该节点右子树的深度self.max = max(self.max, l+r) # 后续遍历更新最大的直径 return max(l,r) + 1 #这也是后序遍历的位置。 # 由于利用后序遍历从低向上计算子问题，其含义是返回当前节点（子节点）中左右子树深度最大的那一个，用于后续计算最大路径。