本文共 7231 字，大约阅读时间需要 24 分钟。

1.找终止条件。 什么情况下递归终止？没得交换的时候，递归就终止了。因此当链表只剩一个结点或者没有结点的时候，自然递归就终止了。

2.找返回值。 我们希望向上一级递归返回什么信息？由于我们的目的是两两交换链表中相邻的结点，因此自然希望交换给上一级递归的是已经完成交换处理，即已经处理好的链表的头结点。

3.本级递归应该做什么。 结合第二步，由于只考虑本级递归，这个链表在我们眼里其实也就三个部分：(head)–>(head->next)–>(已处理完的链表的头结点)。而本级递归的任务也就是交换这3个结点中的前两个结点，就很easy了。

struct ListNode {   	int val;	ListNode *next;	ListNode(int x) : val(x), next(NULL) {   }};class Solution {   public:	ListNode* swapPairs(ListNode* head) {   		if (head == NULL || head->next == NULL)			return head;		//终止条件：链表只剩一个结点或者没结点了，没得交换了。		//找返回值:返回的是已经处理好的链表的头结点		//这个链表在我们眼里其实也就三个部分：(head)-->(head->next)-->(已处理完的链表的头结点)。而本级递归的任务也就是交换这3个结点中的前两个结点		ListNode*temp = head->next;		head->next = swapPairs(temp->next);		temp->next = head;		return temp;	}};

1.找终止条件。 什么情况下递归结束？当然是树为空的时候，此时树的深度为0，递归就结束了。

2.找返回值。 应该返回什么？题目求的是树的最大深度，我们需要从每一级得到的信息自然是当前这一级对应的树的最大深度，因此我们的返回值应该是当前树的最大深度，这一步可以结合第三步来看。

3.本级递归应该做什么。 首先，还是强调要走出之前的思维误区，递归后我们眼里的树一定是这个样子的，此时就三个节点：root、root->left、root->right，其中根据第二步，root->left和root->right分别记录的是root的左右子树的最大深度。那么本级递归应该做什么就很明确了，自然就是在root的左右子树中选择较大的一个，再加上1就是以root为根的子树的最大深度了，然后再返回这个深度即可。

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

class Solution {   public:	int minDepth(TreeNode* root) {   		if (root == NULL)//特判			return 0;		if (root->left == NULL&&root->right == NULL)//递归结束的条件			return 1;		if (root->left == NULL&&root->right != NULL)			return 1 + minDepth(root->right);		if (root->left != NULL&&root->right == NULL)			return 1 + minDepth(root->left);		return min(minDepth(root->left), minDepth(root->right)) + 1;		//注意如果根节点的左或右子树为空的话是构不成子树的。而最小深度是要求从根节点到子树的。当左或右子树为空时，不符合要求。	}};

class Solution {   public:	bool isBalanced(TreeNode* root) {   		if (root == NULL) return true;//递归结束的条件		int d = abs(depth(root->left) - depth(root->right)); //当前结点的左右子树的高度差		return (d <= 1) && (isBalanced(root->left)) && (isBalanced(root->right));	}	// 求解二叉树深度	int depth(TreeNode* node)	{   		if (node == NULL) return 0;//递归结束的条件		return max(depth(node->left), depth(node->right)) + 1;	}};

class Solution {   public:	bool isSymmetric(TreeNode* root) {   		if (root == NULL)			return true;		return isSymmetricCore(root->left, root->right);	}	bool isSymmetricCore(TreeNode* t1, TreeNode* t2) {   		if (t1 == NULL&&t2 == NULL)			return true;		if (t1 == NULL || t2 == NULL)			return false;		if (t1->val != t2->val)			return false;		return isSymmetricCore(t1->left, t2->right) && isSymmetricCore(t1->right, t2->left);	}};

2.想想应该返回什么值：应该返回的自然是已经去重的链表的头节点

3.每一步要做什么：宏观上考虑，此时head->next已经指向一个去重的链表了，而根据第二步，我应该返回一个去重的链表的头结点。因此这一步应该做的是判断当前的head->val和head->next->val是否相等，如果相等则说明重了，返回head->next，否则返回head

class Solution {   public:	ListNode* deleteDuplicates(ListNode* head) {   		if (head == NULL || head->next == NULL)			return head;//返回的是已经去重后的链表的头结点		head->next = deleteDuplicates(head->next);		if (head->val == head->next->val)		{   			ListNode* temp = head->next;			delete head;			return temp;		}		return head;	}};

当然，这题用迭代也很easy:

class Solution {   public:	ListNode* deleteDuplicates(ListNode* head) {   		if (head == NULL)			return head;		ListNode* t = head;		while (t&&t->next)		{   			if (t->val == t->next->val)			{   				ListNode* temp = t->next->next;				delete t->next;				t->next = temp;			}			else			{   				t = t->next;			}		}		return head;	}};

class Solution {   public:	ListNode* reverseList(ListNode* head) {   		if (head == NULL || head->next == NULL)			return head;		ListNode*newhead = reverseList(head->next);//返回的是已经反转的链表的头结点		head->next->next = head;//本级递归应该做的事		head->next = NULL;		return newhead;//返回的是已经反转的链表的头结点	}};

当然，迭代法也很简单！

class Solution {   public:    ListNode* reverseList(ListNode* head) {           if(head==NULL||head->next==NULL)        return head;        ListNode*prev=NULL;        ListNode*cur=head;        while(cur!=NULL)        {               ListNode*temp=cur->next;            cur->next=prev;            prev=cur;            cur=temp;        }        return prev;    }};

class Solution {   public:	TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {   		if (t1 == NULL&&t2 == NULL)			return t1;		if (!t1)			return t2;		if (!t2)			return t1;		t1->val += t2->val;		t1->left = mergeTrees(t1->left, t2->left);		t1->right = mergeTrees(t1->right, t2->right);		return t1;//返回的是已经合并后的子树的根结点	}};

class Solution {   public:	TreeNode* constructMaximumBinaryTree(vector
   
    & nums) {   		if (nums.size() == 0)			return NULL;		int maxIndex = FindMax(nums);		vector
    
     left_nums;		vector
     
      right_nums;		for (int i = 0; i <= maxIndex - 1; i++)			left_nums.push_back(nums[i]);		for (int i = maxIndex + 1; i < nums.size(); i++)			right_nums.push_back(nums[i]);		TreeNode*node = new TreeNode(nums[maxIndex]);		node->left = constructMaximumBinaryTree(left_nums);		node->right = constructMaximumBinaryTree(right_nums);		return node;//返回的是已经构造完毕的子树的根结点	}	int FindMax(vector
      
       &nums) {   		int index = 0, max = nums[0];		for (int i = 0; i < nums.size(); i++) {   			if (nums[i] > max)			{   				max = nums[i];				index = i;			}		}		return index;	}};
      
     
    
   

另一种写法（也是自己稍微改进的哈哈）

class Solution {   public:	TreeNode* constructMaximumBinaryTree(vector
   
    & nums) {   		if (nums.size() == 0)			return NULL;		return constructMaximumBinaryTreeCore(nums, 0, nums.size() - 1);	}	TreeNode* constructMaximumBinaryTreeCore(vector
    
     & nums, int low, int high) {   		if (low > high)			return NULL;		int maxIndex = FindMax(nums, low, high);		TreeNode*node = new TreeNode(nums[maxIndex]);		node->left = constructMaximumBinaryTreeCore(nums, low, maxIndex - 1);		node->right = constructMaximumBinaryTreeCore(nums, maxIndex + 1, high);		return node;//返回的是已经构造完毕的子树的根结点	}	int FindMax(vector
     
      &nums, int low, int high) {   		int index = low, max = nums[low];		for (int i = low + 1; i <= high; i++) {   			if (nums[i] > max)			{   				max = nums[i];				index = i;			}		}		return index;	}};
     
    
   

class Solution {   public:	TreeNode* invertTree(TreeNode* root) {   		if (root == NULL)			return root;				TreeNode*r_l = root->left;		TreeNode*r_r = root->right;		root->left = invertTree(r_r);//返回的是已经完成翻转的子树的根结点		root->right = invertTree(r_l);		return root;	}};

法2：层序遍历

class Solution {   public:	TreeNode* invertTree(TreeNode* root) {   		if (root == NULL)			return NULL;		queue
   
     q;		q.push(root);		TreeNode*temp;		while (!q.empty()) {   			temp = q.front();			q.pop();			swap(temp->left, temp->right);			if (temp->left)				q.push(temp->left);			if (temp->right)				q.push(temp->right);		}		return root;	}};
   

class Solution {   public:	bool hasPathSum(TreeNode* root, int sum) {   		if (root == NULL)			return false;		if (!root->left && !root->right)//叶子结点			return (sum - root->val == 0);		return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);	}};

class Solution {   public:    bool isSameTree(TreeNode* p, TreeNode* q) {          if(p==NULL&&q==NULL)return true;       if(p==NULL||q==NULL)return false;       if(p->val!=q->val)return false;       return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);    }};