关于树的算法一般有两种，递归（Recursion）和迭代（Iteration），下面我会分别列举几种常见的关于树的例子。

首先介绍一下二叉树的结构（如下图）：

image.png

A为根节点（root), D为H，I的父节点（Parent Node）， H，I为D的子节点（Child Node）， H和I之间互为兄弟节点（Sliblings）。树的深度指的是树中有多少个level，图中，树的深度为4。

我们再来介绍一下树的遍历规则，一般的遍历方式有三种，称为前中后序遍历。

image.png

总结一下，就是前中后指的都是根的位置在前中后。

再具体举一个例子（如图）：[1,null,2,3]

image.png

二叉树的结构打印：
TreeNode{val: 1, left: None, right: TreeNode{val: 2, left: TreeNode{val: 3, left: None, right: None}, right: None}}

对于树的代码定义：

# 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

下面看具体的问题：

问题一：二叉树的前序遍历

例题1：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/ 144. 二叉树的前序遍历

思路：

思路一： 迭代（Iteration）， T：O（n）， n为二叉树的节点数； S：O（n）， n为栈的开销
思路二： 递归（Recursion），T：O（n）， n为二叉树的节点数； S：平均情况下为 O(logn)，最坏情况下树呈现链状，为 O(n)。

代码实现：

# 迭代
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        re, stack = [], [root]
        while stack:
            node = stack.pop()
            if node:
                re.append(node.val)
                stack.append(node.right)
                stack.append(node.left)
        return re

# 递归：
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        def dfs(root, res):
            if root:   
                res.append(root.val)
                dfs(root.left, res)
                dfs(root.right, res)
        res = []
        dfs(root, res)
        return res

问题二、求二叉树的最大深度

例题2： https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/ 104. 二叉树的最大深度

思路：

按照总结，常见的思路有两种：递归和迭代。
思路一：递归（Recursion）， 时间复杂度为O（n），其中n为树的节点数 ， 空间复杂度为O（n），其中n为树的深度。
思路二：迭代（Iteration）， 时间复杂度为O（n），其中n为树的节点数 ， 空间复杂度为O（n），其中n为树的深度。

代码实现：

# 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: TreeNode) -> int:
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right)) if root else 0

# 迭代：
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        depth = 0
        stack = [root] if root else []
        while stack:
            depth += 1
            queue = []
            for node in stack:
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            stack = queue
        return depth

撰写记录
2020.12.11-06:11:01-第一次撰写
2020.12.13-08:20:19-第二次撰写