数据结构和算法：二叉树解题思维模式

一：遍历思维（回溯算法核心框架）

是否可以通过遍历二叉树得到答案？
使用一个traverse函数配合外部变量实现。
二叉树遍历框架

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

traverse函数
本质就是遍历二叉树所有节点的一个函数

/* 迭代遍历数组 */
void traverse(int[] arr) {
    for (int i = 0; i < arr.length; i++) {

    }
}


/* 递归遍历数组 */
void traverse(int[] arr, int i) {
    if (i == arr.length) {
        return;
    }
    // 前序位置
    traverse(arr, i + 1);
    // 后序位置
}


/* 迭代遍历单链表 */
void traverse(ListNode head) {
    for (ListNode p = head; p != null; p = p.next) {


    }
}


/* 递归遍历单链表 */
void traverse(ListNode head) {
    if (head == null) {
        return;
    }
    // 前序位置
    traverse(head.next);
    // 后序位置
}

二叉树相当于二叉链表，由于没法写成迭代形式，所以遍历都是递归的形式。

前中后序遍历

1. 前序：刚进入二叉树节点的时候执行
2. 中序：将要离开一个二叉树节点的时候执行
3. 后序：在一个二叉树节点左子树都遍历完，即将开始遍历右子树的时候执行。

二叉树的所有问题就是在前中后序位置中注入巧妙的代码逻辑，去达到目的。
我们只需要单独思考每一个节点应该做什么，其它的交给二叉树遍历框架，它会递归地在所有节点上做相同的操作。

二叉树的最大深度

// 记录最大深度
int res = 0;
// 记录遍历到的节点的深度
int depth = 0;


// 主函数
int maxDepth(TreeNode root) {
    traverse(root);
    return res;
}


// 二叉树遍历框架
void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    // 前序位置
    depth++;
    if (root.left == null && root.right == null) {
        // 到达叶子节点，更新最大深度
        res = Math.max(res, depth);
    }
    traverse(root.left);
    traverse(root.right);
    // 后序位置
    depth--;
}

后序遍历

// 定义：输入一棵二叉树，返回这棵二叉树的节点总数
int count(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftCount = count(root.left);
    int rightCount = count(root.right);
    // 后序位置
    printf("节点 %s 的左子树有 %d 个节点，右子树有 %d 个节点",
            root, leftCount, rightCount);


    return leftCount + rightCount + 1;
}

模板：求最大深度

   // 计算二叉树的最大深度
    int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftMax = maxDepth(root.left);
        int rightMax = maxDepth(root.right);
        return 1 + Math.max(leftMax, rightMax);
    }

层序遍历

模板代码

// 输入一棵二叉树的根节点，层序遍历这棵二叉树
static void levelTraverse(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);//根结点入队列


    while (!q.isEmpty()) {//前面那一轮入队的队列不为空的话
        int sz = q.size();//当前队列结点的总数，即每行的总数
        // 从左到右遍历每一行的节点个数
        for (int i = 0; i < sz; i++) {//每行的所有结点
            TreeNode cur = q.poll();//每次进来循环
            // 将下一层节点放入队列
            if (cur.left != null) {
                q.offer(cur.left);
            }
            if (cur.right != null) {
                q.offer(cur.right);
            }
        }
    }
}

二：分解问题思维（动态规划核心框架）

是否可以定义一个递归函数，通过子树推导出原问题答案？
写出递归函数的定义，利用这个函数的返回值

二叉树的构造

二叉树的构造问题一般都是使用「分解问题」的思路：

构造整棵树 = 根节点 + 构造左子树 + 构造右子树。