树的子结构

一直对递归用的太机械，每写一个递归都想一下子想到方方面面，扣清除每个位置的语句运行时会发生什么，本是优点，但是由于递归的深度，完全靠大脑想象整个过程相当复杂。 最近看到了剑指offer上的两个递归题（我想过用别的方法，但是没想出来，也没查出来，而且好的递归函数逻辑性很强），感觉如果建模建的好，逻辑清晰，递归真的是很方便的。但是建模建的好，逻辑清晰不是说说就有的，需要锻炼。

题目一：树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。

如图A树和B树，先将A树根和B树根进行比较，相等，继续将A树左子树和B树左子树比较，不相等，当前这次比较结束。将A的左子树为根，继续重复上面的比较工作，若存在B树结构则返回TRUE；不存在的话，以A的右子树为根和B树进行比较。 总结:上面有两个递归过程，

第一个是整体上的：以当前节点为根与B树比较，若比较结果为真则返回TRUE；否则，以当前节点左子树结点为根进行比较，为真返回TRUE；否则，以当前结点右子树结点为根继续判断。

bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {//B树为空返回FALSE if (pRoot2 == NULL) return false; //A树结点为空 if (pRoot1 == NULL){ return false; } bool result = false; //不为真就一直往下比较，为真就退出。 result = isSubTree(pRoot1, pRoot2); if (!result){//避免了已经找到子结构还继续判断的情况 result = HasSubtree(pRoot1->left, pRoot2); } if (!result){ result = HasSubtree(pRoot1->right, pRoot2); } return result; } ``` 第二个是比较的过程：若A树当前结点与B树当前结点相同，比较A树当前结点左子树中是否有B树当前结点左子树结构，A树当前结点右子树中是否有B树当前结点右子树的结构，若均有返回TRUE。 : bool isSubTree(TreeNode*pRoot1, TreeNode*pRoot2){ if (pRoot2 == NULL) return true; if (pRoot1 == NULL){ return false; } if (pRoot1->val == pRoot2->val){ //return isSubTree(pRoot1->left, //pRoot2->left)&& //isSubTree(pRoot1->right,pRoot2->right); if (isSubTree(pRoot1->left, pRoot2->left)){ if (isSubTree(pRoot1->right, pRoot2->right)) return true; } } return false; }

没有直接用剑指offer中的代码第一是因为理解了，第二是认为分别判断左右子树是否isSubTree有一个好处就是如果左子树存在不同，就可以直接返回FALSE，不用再判断右子树。虽然节省了一点点，但也是改进:)。

合并排序链表

这个题在我看来真的要和出题人沟通，其实有很多省事的办法，如果最后返回的链表可以是重新创造的数组的话，这个问题完全可以用数组合并排序的方式；如果不可以，还是老老实实按照递归的模型走吧 时间不多，上代码：

ListNode* Merge(ListNode* pHead1, ListNode* pHead2) { if (pHead1 == NULL) return pHead2; if (pHead2 == NULL) return pHead1; ListNode*current; if (pHead1->val < pHead2->val){ current = pHead1; pHead1 = pHead1->next; } else{ current = pHead2; pHead2 = pHead2->next; } current->next = Merge(pHead1, pHead2); return current; }

每次求剩余两个链表的最小结点，返回；需要的注意的是，链表中一定不要忘记了结点之间的连接关系。