算法随想Day17【二叉树】| 二叉树题目的递归解法总结

总结思考：

目前涉及基于二叉树的特性，进行递归的方案有如下：

左右子树不相干的递归

回溯，左右子树不相干的递归：用前序遍历，先处理"中"节点，判断是否达到终止条件进行相关处理（终止条件为 if(root == nullptr) 或者 if(root->left == nullptr && root->right == nullptr) -- 视情况而定），后面分别递归左右子树，两者平行不相干。（LC112. 路径总和、LC257. 二叉树的所有路径）

1. LC226-翻转二叉树，当前节点下的left和right再操作，两者平行，互不干扰。

////翻转二叉树
TreeNode* invertTree(TreeNode* root)
{
    if (root == nullptr)
    {
        return root;
    }
    swap(root->left, root->right);  //中
    invertTree(root->left);  //左
    invertTree(root->right);  //右
    return root;
}

2. LC257-二叉树的所有路径，对当前节点来说，对左右子树分别进行递归搜集路劲，是平行独立进行的，不会相互干扰。

void traversal(TreeNode* cur, string path, vector<string>& result)
{
    path += to_string(cur->val); // 中
    if (cur->left == NULL && cur->right == NULL)
	{
        result.push_back(path);
        return;
    }
    if (cur->left) 
		traversal(cur->left, path + "->", result); // 左
	if (cur->right) 
		traversal(cur->right, path + "->", result); // 右
}

vector<string> binaryTreePaths(TreeNode* root)
{
    vector<string> result;
    string path;
    if (root == NULL) return result;
    traversal(root, path, result);
    return result;
}

3. LC112-路径总和，将当前节点的值+=入sum中后，对左子树递归相加完，回溯时sum值还是保持不变，接下来再往右子树去递归，这是一个深入递归试探，若不成功，回溯再试探的过程，不管是往左还是往右深入，都是独立的过程。

int flag;
void checkPathSum(TreeNode* root, int sum, int& targetSum)
{
    if (root == nullptr) return;  //力扣非要加多这一句才给通过，不理解
    sum += root->val;  //中
    if (root->left == nullptr && root->right == nullptr)
    {
        if (targetSum == sum)
        {
            flag = true;
        }
        return ;
    }
    checkPathSum(root->left, sum, targetSum);  //左
    checkPathSum(root->right, sum, targetSum);  //右
}
bool hasPathSum(TreeNode* root, int targetSum)
{
    int sum = 0;
    flag = false;
    if (root == nullptr)
    {
        return false;
    }
    checkPathSum(root, sum, targetSum);
    return flag;
}

4. LC513-找树左下角的值，这道题的递归解法比较巧妙，变量maxDepth记录当前的最深的层次，而且在最深层，找到第一个叶子节点，才会进行存储并更新maxDepth。用到回溯，保持当前节点回溯时和递归前的depth值一致。本题对深层遍历的要求只要是左子树先于右子树即可，两个也不互相干扰。

class Solution {
public:
    int maxDepth = INT_MIN;
    int result;
    void traversal(TreeNode* root, int depth) {
        if (root->left == NULL && root->right == NULL) {
            if (depth > maxDepth) {
                maxDepth = depth;
                result = root->val;
            }
            return;
        }
        if (root->left) {
            depth++;
            traversal(root->left, depth);
            depth--; // 回溯
        }
        if (root->right) {
            depth++;
            traversal(root->right, depth);
            depth--; // 回溯
        }
        return;
    }
    int findBottomLeftValue(TreeNode* root) {
        traversal(root, 0);
        return result;
    }
};

左右子树相干的递归

左右子树相干的递归：在对当前节点的左右子树都递归完后，回溯到当前节点时，处理的值会跟左右两子树的返回值(引用值)都相关。

1. LC104-二叉树的最大深度，在递归完左右子树后，回溯到当前节点，会进行左右子树的深度比较

int maxdepth(treenode* root)
{
    int leftdepth = 0, rightdepth = 0;
    if (root == null)
    {
        return 0;
    }
    leftdepth = maxdepth(root->left);
    rightdepth = maxdepth(root->right);
    int middledepth = max(leftdepth, rightdepth) + 1;
    return middledepth;
}

2. 二叉树的节点个数，当前节点的计数值，等于左右子树递归返回值之和 + 当前当前节点的1个

int countNodes(TreeNode* root)
{
    if (root == nullptr)
    {
        return 0;
    }
    int leftnum = countNodes(root->left);
    int rightnum = countNodes(root->right);
    int midnum = leftnum + rightnum + 1;
    return midnum;
}

3. LC110-平衡二叉树，对左右子树递归分别的返回值，进行绝对值之差的对比

bool flag;
int checkBalanced(TreeNode* root)
{
    if (root == nullptr)
    {
        return 0;
    }
    int leftheight = checkBalanced(root->left);
    int rightheight = checkBalanced(root->right);
    if (abs(leftheight - rightheight) > 1)
    {
        flag =  false;
    }
    int midheight = max(leftheight, rightheight) + 1;
    return midheight;
}
bool isBalanced(TreeNode* root)
{
    flag = true;
    checkBalanced(root);
    return flag;
}

4. LC404-左叶子之和，回溯到当前节点时，对sum值的维护同样需要左右子树递归值的共同参与，只不过是加了一些条件而已，如sum = leftsum + rightsum + (root->left == nullptr && root->right == nullptr && is_left == 1 ? root->val : 0);

int sumOfLeftLeaves(TreeNode* root)
{
    int sum = 0;
    int leftsum = 0, rightsum = 0;
    if (root == nullptr)
    {
        return sum;
    }
    if (root->left != nullptr)
    {
        leftsum += sumOfLeftLeaves(root->left);
    }
    if (root->right != nullptr)
    {
        rightsum += sumOfLeftLeaves(root->right);
    }
    sum = leftsum + rightsum + (root->left == nullptr ? 0 : root->left->val);
    return sum;
}