有关二叉树的算法——（二叉树遍历）

有关二叉树的算法——（二叉树遍历） 二叉树（第一期） 1. 深入理解前中后序

二叉树代码框架

void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    // 前序位置
    traverse(root.left);
    // 中序位置
    traverse(root.right);
    // 后序位置
}

2. 二叉树的重要性

举个例子，比如说我们的经典算法【快速排序】和【归并排序】，对于这两个算法，是怎么理解的？说白了，快速排序就是二叉树的前序遍历，而归并排序就是二叉树的后序遍历。

为什么快速排序和归并排序能和二叉树扯上关系？接下来分以下一下算法思想和代码框架：

2.1 快速排序

快速排序： 若要对 nums[lo...hi] 进行排序，我们先找一个分界点 p，通过交换元素使得 nums[lo..p1] 都小于等于 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);
}

先构建分界点，然后去左右子数组构造分界点。

2.2 归并排序

归并排序： 若要对 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);
    
}

先对有右子数组排序，然后合并（类似合并链表的逻辑）

3. 写递归算法的秘诀

我们写递归算法的关键是要明确函数的【定义】是什么，然后相信这个定义，利用这个定义推导最终结果，绝不要跳入递归的细节

简单看几行代码：

// 定义：count(root) 返回以 root 为根的树有多少节点
int count(TreeNode root) {
    // base case
    if (root == null) return 0;
    // 自己加上子树的节点就是整棵树的节点树
    return 1 + count(root.left) + count(root.right);
}

这个问题，root 本身就是一个节点，加上左右子树的节点数就是以root为根的树的节点总数。

左右子树的节点数怎么算？其实就是计算根为 root.left 和 root.right 两棵树的节点树呗，按照定义，递归调用 count 函数即可算出来。

写树相关的算法，简单说就是，先搞清楚当前root 节点【该做什么】以及【什么时候做】，然后根据函数定义递归调用子节点，递归调用会让孩子节点做相同的事情。

4. 算法实践 4.1 第一题：翻转二叉树

     4
   /   
  2     7
 /    / 
1   3 6   9

反转之后的样子

     4
   /   
  2     7
 /    / 
1   3 6   9

通过观察，发现就是从中心竖线进行一次镜像反转

代码实现

TreeNode inverTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    
    // root 节点需要交换它的左右子节点
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    
    // 让左右子节点继续反转他们的子节点
    inverTree(root.left);
    inverTree(root.right);
    
    return root;
}

关键思路在于我们发现反转整棵树就是交换每个节点左右子节点，因此把交换左右子节点的代码放在了前序遍历的位置。

二叉树树题目的一个难点就是，如何把题目的要求细化成每个节点需要做的事情。

4.2 第二题：填充二叉树节点的右侧指针

题目：给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下

class Node {
    int val;
    Node left;
    Node right;
    Node next;
}

填充它的每个 next 指针，让这个指针想其下一个右侧节点，如果找不到下一个右侧节点，则将 next 指针设为 null。

Node connect(Node root) {
    if (root == null || root.left == null) {
        return root;
    }
    root.left.next = root.right;
    connect(root.left);
    connect(root.right);
    return root;
}

这样看似已经大功完成了，但是存在一些问题，节点 5 和节点 6 不属于同一父节点，那么按照这段代码逻辑，它俩就没办法被穿起来。

二叉树的难点在于，如何把题目的要求细化成每个节点需要做的事情，但是如果只依赖于一个节点的话，肯定是没办法跨父节点的两个相邻节点。

那么，一个节点做不到，我们就用两个节点，将每一层二叉树节点连接起来可以细化成将每两个相邻节点都连接起来

Node connect(Node root) {
    if (root == null) {
        return null;
    }
    connectTwoNode(root.left, root.right);
    return root;
}
public void connectTwoNode(Node node1, Node node2) {
    if(node1 == null || node2 == null) {
        return;
    }
    
    // 将传入的两个节点连接
    node1.next = node2;
    
    // 连接相同父节点的两个子节点
    connectTwoNode(node1.left, node1.right);
    connectTwoNode(node2.left, node2.right);
    // 连接跨越父节点的两个子节点
    connectTwoNode(node1.right, node2.left);
}

4.3 第三题：将二叉树展开为链表

我们给函数输入一个节点 root ，那么以 root 为根的二叉树就会被拉平为一条链表。

实现步骤：

将 root 的左子树和右子树拉平。将 root 的右子树接到左子树下方，然后将整个左子树作为右子树。

void flatten(TreeNode root) {
 	// base case
    if(root == null) {
        return;
    }
    flatten(root.left);
    flatten(root.right);
    
    // 1. 左右子树已经被拉平成一条链表
    TreeNode left = root.left;
    TreeNode right = root.right;
    // 2. 将左子树作为右子树
    root.left = null;
    root.right = left;
    
    // 3. 将原先的右子树接触到当前右子树的末端
    TreeNode p = root;
    while (p.right != null) {
        p = p.right;
    }
    p.right = right;
}

递归的魅力：我们只要知道让 root 做它该做的事情，然后，flatten 函数就会按照定义工作。递归框架是后序遍历，因为我们要先拉平右子树才能后续 *** 作。

4.4 总结

递归算法的关键要明确函数的定义，相信这个定义，而不要跳进递归细节。

写二叉树的算法题，都是基于递归框架的，我们先要搞清楚 root 节点它自己要做什么，然后根据题目要求选择使用前序，中序，后续的递归框架。

二叉树题目的难点在于如果通过题目的要求思考出每一个节点需要做什么，这个多做一些题目进行练习就OK了。