【LeetCode】101. Symmetric Tree

今天在LeetCode上写了两道关于二叉树递归的题目，分别是101和 112，在这里想小小的总结一下。

首先是101：

给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   /  \
  2    2
 / \   / \
3   4 4   3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

     1
    / \
   2   2
   \    \
    3    3

题目分析：
看到这道题首先想到的是分两条路，传递参数递归判断就好了。
既然用到了递归，首先要思考终止递归的判断。在这里，每条路走到叶子节点便停止了，具体代码如下：

class Solution
{
  public:
    bool isSymmetric(TreeNode *root)
    {
        if(root==NULL)return true;   //如果传入的树为空树，返回true
        return symmetric(root->left, root->right);
    }
    bool symmetric(TreeNode *l, TreeNode *r)  //两个节点分别对比，为了方便简写成l和r
    {
        if(l==NULL&&r==NULL)    //如果左右节点都为空，则返回true
            return true;
        if(l==NULL||r==NULL)    //如果只有一个为空，那么肯定不对称，返回false
            return false;
        if(l->val!=r->val)      //如果值不等，也是不对成，返回false
            return false;
        else{
            /*
             *下面可以说是递归的主体，注意左右两边的节点是对称判断的，例如左边的右节点对应右边的左节点
             */
            return symmetric(l->left, r->right) && symmetric(r->left, l->right);
        }
    }
};

然后我们看到112：

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及目标和 sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

题目分析：这里也是需要用到递归思路（其他方法也可以，但是我更喜欢递归哈哈），函数接受一个节点和目标值，我们在递归过程中传入下一个节点与另一个目标值，另一个目标值就是当前值减去当前节点的值（我说的好像有点拗口。。），所以在往下递归过程中，当到了叶子节点时，我们只需要判断叶子节点的值等不等于传入值了。具体代码如下：

class Solution
{
  public:
    bool hasPathSum(TreeNode *root, int sum){  
        if(root==NULL)              //如果传递进来的是空树，则肯定为false
            return false;
        return hasPathSum2(root, sum);    
    } 
    bool hasPathSum2(TreeNode *root, int sum)  //因为要判断是否为空树，所以递归函数另写了，名字也偷懒起了，不要学我哈哈
    {   
        if(root->left==NULL&&root->right==NULL)   //如果该节点是叶子节点（左右都为空）
            return root->val == sum;              //判断是否为目标值并返回结果
        if(root->left==NULL||root->right==NULL){   //如果有一个为非空

            if(root->left!=NULL)
                return hasPathSum2(root->left, sum - root->val);
            else
                return hasPathSum2(root->right, sum - root->val);
        }
        else{                                         //如果两个都不为空，继续递归
            return hasPathSum2(root->left, sum - root->val) || hasPathSum2(root->right, sum - root->val);
        }
    }
};

小节：
其实这两道题都是二叉树中的递归，很相似，又有些许不同，例如在最后的return后面同样是调用的两个函数，一个是&&（与）连接词，一个是||（或）连接词。因为在判断对称的过程中，所有的节点都要求对称，所以必须用&&，而目标值中，只要有一条路径的和是非就达到条件了，所以用||。
这些都是一些在递归之中很微妙的特点。另外，这两道题共同的特点就是递归终止条件不单一（这是我个人的理解），例如一些像斐波拉契数列之类的，递归终止条件就只有一个，一个if就够了，而这两道题之中都需要多次判断，这里需要我们细心一点思考如果编写终止条件。
另外记住bool函数的递归中，递归写法差不多应该是 return XXX();//XXX是递归函数名。这点的话不知道普适性如何？
好了，以上就是我的总结。