翻转二叉树

. 题意：翻转一棵二叉树。 思路：直接遍历树，然后翻转当前节点的左右节点。

class Solution {
          
   
public:
    TreeNode* invertTree(TreeNode* root) {
          
   
        if (root == NULL) return root;
        swap(root->left, root->right);  // 中
        invertTree(root->left);         // 左
        invertTree(root->right);        // 右
        return root;
    }
};

对称二叉树

. 题意：给定一个二叉树，检查它是否是镜像对称的。 思路：关键是镜像对称，比较的就不是左右节点，而是最里面和最外面的节点。

class Solution {
          
   
public:
    bool compare(TreeNode* left, TreeNode* right) {
          
   
        // 首先排除空节点的情况
        if (left == NULL && right != NULL) return false;
        else if (left != NULL && right == NULL) return false;
        else if (left == NULL && right == NULL) return true;
        // 排除了空节点，再排除数值不相同的情况
        else if (left->val != right->val) return false;

        // 此时就是：左右节点都不为空，且数值相同的情况
        // 此时才做递归，做下一层的判断
        bool outside = compare(left->left, right->right);   // 左子树：左、 右子树：右
        bool inside = compare(left->right, right->left);    // 左子树：右、 右子树：左
        bool isSame = outside && inside;                    // 左子树：中、 右子树：中 （逻辑处理）
        return isSame;

    }

    bool isSymmetric(TreeNode* root) {
          
   
        if(root==nullptr) return true;
        return compare(root->left, root->right);
    }
};

平衡二叉树

. 题意：给定一个二叉树，判断它是否是高度平衡的二叉树。 思路：平衡二叉树，一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

class Solution {
          
   
public:
    bool isBalanced(TreeNode* root) {
          
   
        return getDepth(root) == -1 ? false : true;
    }
    int getDepth(TreeNode* node){
          
   
        if(node==nullptr) return 0;
        int leftDepth = getDepth(node->left);
        if (leftDepth == -1) return -1; // 说明左子树已经不是二叉平衡树
        int rightDepth = getDepth(node->right);
        if (rightDepth == -1) return -1; // 说明右子树已经不是二叉平衡树
        return abs(leftDepth - rightDepth) > 1 ? -1 : 1 + max(leftDepth, rightDepth);
    }
};

路径总和

. 题意：给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。 思路：用result存放满足条件的路径，用一个path存放路径，sum用来累计路径和，每记录完一次路径，回溯一下，sum减去当前节点值，path pop末尾元素。判断result是否为空，为空则不存在，否则存在。

class Solution {
          
   
public:
    vector<vector<int>> result;
    vector<int> path;
    int sum=0;
    void Sum(TreeNode* root, int targetSum){
          
   
        sum+=root->val;
        path.push_back(root->val);
        if(root->left==nullptr&&root->right==nullptr&&sum==targetSum){
          
   
            result.push_back(path);
        }
        if(root->left){
          
   
            Sum(root->left,targetSum);
            sum-=root->left->val;
            path.pop_back();
        }
        if(root->right){
          
   
            Sum(root->right,targetSum);
            sum-=root->right->val;
            path.pop_back();
        }
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
          
   
        if(root==nullptr) return false;
        Sum(root,targetSum);
        return size(result)!=0;
    }
};