二叉树 – 技巧和注意事项

• 1 遍历篇。是否可以通过遍历一遍二叉树得到答案（DFS或者BFS），用一个traverse配合外部变量来实现。
• 2 分解篇。是否可以通过定义一个递归函数，通过子问题（子树）的答案推导处原问题的答案，并充分利用这个递归函数的返回值。

1 遍历思想和分解思想的差异

• 1 遍历思想。
  • 1.1 函数定义返回值：void；
  • 1.2 遍历方式：前序遍历；
  • 1.3 遍历模式：自顶向下
  • 1.4 参数使用：一般都是只能使用来自根节点的参数；
  • 1.5 使用场景：二叉树 + 回溯
• 2 分解思想
  • 2.1 函数定义返回值：TreeNode*；
  • 2.2 遍历方式：后序遍历；
  • 2.3 遍历模式：自底向上；
  • 2.4 参数使用：除了来自根节点的参数之外还有子树返回的参数；
  • 2.5 使用场景：二叉树+动态规划

2 思维模式的思考

• 1 如果单独抽取一个二叉树节点，它需要做什么事情？需要在什么时候（前/中/后序位置）做？其他节点不用操心，递归函数会帮忙在所有节点上执行相同的操作。
• 2 二叉树的所有问题，都是在前中后序位置注入巧妙的代码逻辑，达到自己的目的。
• 3 中序遍历用于二叉搜索树。
• 4 一旦你发现题目和子树有关，那大概率要给函数设置合理的定义和返回值，在后序位置写代码了。

3 深度理解前中后序遍历

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

4 真题演练

4.1 二叉树的最大深度

4.1.1 遍历思想

• 1 函数定义返回值：void
• 2 遍历方式：前序遍历
• 3 遍历模式：自顶向上
• 4 参数使用：只能通过来自根节点的depth

class Solution {
public:
    int depthMax = 0;
    void getDepth(TreeNode* root, int depth){
        if (root == nullptr) return ;
        depth++;
        depthMax = max(depth, depthMax);
        getDepth(root->left, depth);
        getDepth(root->right, depth);
    }

    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        getDepth(root, 0);
        return depthMax;
    }
};

4.1.2 分解思想

• 1 函数定义返回值：int
• 2 遍历方式：后序遍历
• 3 遍历模式：自自底向上
• 4 参数使用：除了来自根节点的信息之外，还能获取来自左右子树的depth

class Solution {
public:
    int getDepth(TreeNode* root){
        if (root == nullptr) return 0;
        int left = getDepth(root->left);
        int right = getDepth(root->right);
        return max(left, right) + 1;
    }

    int maxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        return getDepth(root);
    }
};

4.2 二叉树的直径

4.2.1 遍历思想

class Solution {
    // 记录最大直径的长度
    int maxDiameter = 0;
public:
    int diameterOfBinaryTree(TreeNode* root) {
        // 对每个节点计算直径，求最大直径
        traverse(root);
        return maxDiameter;
    }

    // 遍历二叉树
    void traverse(TreeNode* root) {
        if (root == nullptr) {
            return;
        }
        // 对每个节点计算直径
        int leftMax = maxDepth(root->left);
        int rightMax = maxDepth(root->right);
        int myDiameter = leftMax + rightMax;
        // 更新全局最大直径
        maxDiameter = max(maxDiameter, myDiameter);
        
        traverse(root->left);
        traverse(root->right);
    }

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

4.2.2 分解思想

class Solution {
    // 记录最大直径的长度
    int maxDiameter = 0;

public:
    int diameterOfBinaryTree(TreeNode* root) {
        maxDepth(root);
        return maxDiameter;
    }

    int maxDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        int leftMax = maxDepth(root->left);
        int rightMax = maxDepth(root->right);
        // 后序位置，顺便计算最大直径
        int myDiameter = leftMax + rightMax;
        maxDiameter = max(maxDiameter, myDiameter);

        return 1 + max(leftMax, rightMax);
    }
};