Day 14 二叉树: 遍历 (前中后：递归|迭代), 543. Diameter of Binary Tree

满二叉树

二叉搜索树

平衡二叉搜索树
二叉树存储 (链式，数组）

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

二叉树遍历 (递归，迭代），本质是深搜(dfs).
- 前序: 中左右 (pre-order)
- 中序: 左中右 (in-order)
- 后序: 左右中 (post-order)

144. 二叉树的前序遍历

思路
- example
- 递归
复杂度. 时间：O(n), 空间: O(n)

中左右

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def traversal(root):
            if root == None:
                return 
            res.append(root.val)
            traversal(root.left)
            traversal(root.right)
        res = []
        traversal(root)
        return res

迭代
- 用list实现stack, 每次从stack pop一个node出来进行处理。
- 然后node.right先入栈，node.left后入栈（进栈：先右后左；出栈：先左后右）。
  - 空节点不入栈

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root == None:
            return []
        res = []
        stack = [root]
        while stack:
            node = stack.pop()
            res.append(node.val) # node cannot be None
            if node.right:
                stack.append(node.right) 
            if node.left:
                stack.append(node.left)
        return res

迭代“统一”写法, 真正自然写法。
- 利用stack和cur遍历 stack作为辅助
  - 一条道走到黑。
  - 走不动再从stack pop出来换方向（左-->右）。

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        cur = root
        stack = []
        res = []
        while cur or stack:
            if cur:
                res.append(cur.val)
                stack.append(cur)
                cur = cur.left 
            else:
                cur = stack.pop()
                cur = cur.right 
        return res

94. 二叉树的中序遍历

思路
- example
- 递归
复杂度. 时间：O(n), 空间: O(n)

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def traversal(root):
            if root == None:
                return
            traversal(root.left)
            res.append(root.val)
            traversal(root.right)
        res = []
        traversal(root)
        return res

迭代''统一''写法

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        cur = root 
        stack, res = [], []
        while cur or stack:
            if cur:
                stack.append(cur) 
                cur = cur.left 
            else:
                cur = stack.pop()
                res.append(cur.val) 
                cur = cur.right 
        return res

145. 二叉树的后序遍历

思路
- example
- 递归
复杂度. 时间：O(n), 空间: O(n)

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def traversal(root):
            if root == None:
                return
            traversal(root.left)
            traversal(root.right)
            res.append(root.val)
        res = []
        traversal(root)
        return res

迭代
- 类似前序迭代遍历，利用对称性，反转结果list.
  - 中右左 --> 左右中

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root == None:
            return []
        res = []
        stack = [root]
        while stack:
            node = stack.pop()
            res.append(node.val)
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        res.reverse()
        return res

迭代''统一''写法

中右左反转成左右中

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        cur = root
        res, stack = [], []
        while cur or stack:
            if cur:
                res.append(cur.val)
                stack.append(cur)
                cur = cur.right 
            else:
                cur = stack.pop()
                cur = cur.left
        res.reverse()  # !!!
        return res

应用

快速排序: 二叉树的前序遍历

对 nums[lo..hi] 进行排序，我们先找一个分界点 p，通过交换元素使得 nums[lo..p-1] 都小于等于 nums[p]，且 nums[p+1..hi] 都大于 nums[p]，然后递归地去 nums[lo..p-1] 和 nums[p+1..hi] 中寻找新的分界点，最后整个数组就被排序了。

void sort(int[] nums, int lo, int hi) {
    /****** 前序遍历位置 ******/
    // 通过交换元素构建分界点 p
    int p = partition(nums, lo, hi);
    /************************/

    sort(nums, lo, p - 1);
    sort(nums, p + 1, hi);
}

归并排序: 二叉树的后序遍历

对 nums[lo..hi] 进行排序，我们先对 nums[lo..mid] 排序，再对 nums[mid+1..hi] 排序，最后把这两个有序的子数组合并，整个数组就排好序了。

// 定义：排序 nums[lo..hi]
void sort(int[] nums, int lo, int hi) {
    int mid = (lo + hi) / 2;
    // 排序 nums[lo..mid]
    sort(nums, lo, mid);
    // 排序 nums[mid+1..hi]
    sort(nums, mid + 1, hi);

    /****** 后序位置 ******/
    // 合并 nums[lo..mid] 和 nums[mid+1..hi]
    merge(nums, lo, mid, hi);
    /*********************/
}

二叉树题目的递归解法可以分两类思路
- 第一类是遍历一遍二叉树得出答案 (回溯）
- 第二类是通过分解问题计算出答案（动规）

543. Diameter of Binary Tree

思路
- example
- 递归: 后序遍历（自下而上）

递归返回值：以当前节点为root的子树的深度。
同时维护一个全局变量（或者递归参数）更新答案|直径。

每一条二叉树的「直径」长度，就是一个节点的左右子树的最大高度之和。遍历整棵树中的每个节点，然后通过每个节点的左右子树的最大深度算出每个节点的「直径」，最后把所有「直径」求个最大值即可。
遇到子树问题，首先想到的是给函数设置返回值，然后在后序位置做文章。
是否可以通过遍历一遍二叉树得到答案？如果不能的话，是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案? 如果需要涉及到子树信息, 建议使用后续遍历.
本题：后序遍历的例题使用了「分解问题」的思路。因为当前节点接收并利用了子树返回的信息，这就意味着你把原问题分解成了当前节点 + 左右子树的子问题。
二叉树的「直径」长度，就是任意两个结点之间的路径长度。最长「直径」并不一定要穿过根结点：

复杂度. 时间：O(n), 空间: O(n)

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        def traversal(root):
            nonlocal res 
            if root == None:
                return 0
            left_diameter = traversal(root.left)
            right_diameter = traversal(root.right)
            cur_diameter = left_diameter + right_diameter  
            res = max(res, cur_diameter)
            return max(left_diameter, right_diameter) + 1 # 以root为其中一个端点的最大diameter 
        res  = 0
        traversal(root)
        return res

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        def traversal(root):
            nonlocal res 
            if root == None:
                return 0
            left = traversal(root.left) 
            right = traversal(root.right) 
            res = max(res, left+right) 
            return max(left, right)+1
        res = 0 
        traversal(root)
        return res