二叉树-第一期

/* 二叉树遍历框架 */
void traverse(TreeNode root) {
    // 前序遍历
    traverse(root.left)
    // 中序遍历
    traverse(root.right)
    // 后序遍历
}

快速排序的逻辑是，若要对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]排序，最后把这两个有序的子数组合并，整个数组就排好序了。
归并排序就是二叉树的后序遍历

void sort(int[] nums, int lo, int hi) {
    int mid = (lo + hi) / 2;
    sort(nums, lo, mid);
    sort(nums, mid + 1, hi);

    /****** 后序遍历位置 ******/
    // 合并两个排好序的子数组
    merge(nums, lo, mid, hi);
    /************************/
}

226 翻转二叉树

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return root
        
        left = root.left
        root.left = root.right
        root.right = left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

116 填充二叉树的右侧指针

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return root
        
        left = root.left
        root.left = root.right
        root.right = left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

这样5-6无法串起来，所以，仅仅依靠一个节点无法解决该问题。需要增加参数节点，

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root or not root.left:
            return root
        root.left.next = root.right
        if root.next:
            root.right.next = root.next.left 

        self.connect(root.left)
        self.connect(root.right)
        return root