目录

 一、遍历思维模式

 543. 二叉树的直径

二、分解问题思维模式

114. 二叉树展开为链表

一旦发现题目和子树有关，大概率要给函数设置合理的定义和返回值，在后序位置写代码了。

二叉树解题的思维模式分两类（来源：labuladong）：

1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse 函数配合外部变量来实现，这叫「遍历」的思维模式。

2、是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值，这叫「分解问题」的思维模式。

无论使用哪种思维模式，你都需要思考：

如果单独抽出一个二叉树节点，它需要做什么事情？需要在什么时候（前/中/后序位置）做？其他的节点不用你操心，递归函数会帮你在所有节点上执行相同的操作。

 一、遍历思维模式

 543. 二叉树的直径

int max_diameter;
    int diameterOfBinaryTree(TreeNode* root) {
        MaxDepth(root);
        return max_diameter;
    }
    // 最大直径是左右结点深度和
    int MaxDepth(TreeNode* node) {
        if (!node)   return 0;
        int left_max = MaxDepth(node->left);
        int right_max = MaxDepth(node->right);
        // 遍历最大深度的同时，由于是后序遍历，顺便可以得到但前结点处的最大直径
        int cur_diameter = left_max + right_max;
        max_diameter = max(max_diameter, cur_diameter);
        return 1 + max(left_max, right_max);
    }

每一条二叉树的「直径」长度，就是一个节点的左右子树的最大深度之和。借助后序遍历求最大深度的方法，利用全局变量记录最大元素，一次遍历即可获得结果。

二、分解问题思维模式

114. 二叉树展开为链表

// 分治思想，把子树展开为链表
    void flatten(TreeNode* root) {
        if (!root)   return;
        // 后序遍历
        flatten(root->left);
        flatten(root->right);
        // 当存在左子树时，把右子树接到左子树的右侧叶节点上
        if (root->left) {
            TreeNode* cur = root->left;
            while (cur->right)   cur = cur->right;
            cur->right = root->right;
            root->right = root->left;
            root->left = nullptr;
        }
        return;
    }

注意本题的返回值为void类型，说明题目希望在原地完成拉直操作，分解思想可以解决本问题。

如下图所示（来源：labuladong），对于一个节点 x，可以执行以下流程：

1、先利用 flatten(x.left) 和 flatten(x.right) 将 x 的左右子树拉平。

2、将 x 的右子树接到左子树下方，然后将整个左子树作为右子树。