算法——二叉树类

二叉树类的算法有两条解题思路。选一个就能解题

1. 思路（一）：这也是我最常用的思路。只针对根节点和其左右子树（把左右子树各看成一个节点就行）解决当前问题，就像下面这样。这样就避免了对递归的考虑

1）边界：考虑是一颗空树时的情况（root==null）

2）再考虑对根节点的处理，对左子树的处理，对右子树的处理

2. 思路（二）：递归思想。

1）递归出口：叶子结点

2）再考虑对根节点的处理，对左子树的处理，对右子树的处理

这些例题我都是用第一个思路去做的，也在注释上标明了思路。

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        //1.空树
        if(root==NULL)  return NULL;  

        //2.根节点不用考虑

        //3.考虑左子树和右子树的处理
        TreeNode* left=invertTree(root->right);  //left是翻转后应该在left的
        TreeNode* right=invertTree(root->left);  //right是翻转后应该在right的
        root->right=right;
        root->left=left;
        return root;       //!!!最后返回整棵树的根节点
    }
};

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        //1.空树
        if(p==nullptr&&q==nullptr) return true;  //空树1
        else if(p==nullptr&&q!=nullptr) return false; //空树2
        else if(p!=nullptr&&q==nullptr) return false; //空树3
        
        //2.这里把根节点、左子树、右子树的处理一起考虑了
        else{
            return (p->val==q->val&&isSameTree(p->left,q->left)&&isSameTree(p->right,q->right));
        }
    }
};

这个题注意看一下最后一个示例3。

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        //1.空树
        if(root==nullptr) return false; 

        //2.考虑根节点的处理
        if(root->left==nullptr&&root->right==nullptr&&targetSum==root->val) return true;

        //3.考虑对左子树、右子树的处理
        int left = targetSum - root->val;
        return hasPathSum(root->left,left)||hasPathSum(root->right,left);
    }
};