普通版剑指 Offer 浅刷浅刷( 六 ) _数组

/*** Definition for singly-linked list.* struct ListNode {*int val;*ListNode *next;*ListNode(int x) : val(x), next(NULL) {}* };*///方法一：class Solution {public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {if (!l1) {return l2;}if (!l2) {return l1;}if (l1->val > l2->val) {l2->next = mergeTwoLists(l1, l2->next);return l2;} else {l1->next = mergeTwoLists(l1->next, l2);return l1;}}};//方法二：class Solution {public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode *returnList = new ListNode();ListNode *temp = returnList;while (l2 || l1) {if (!l1) {temp->next = l2;break;}if (!l2) {temp->next = l1;break;}if (l1->val > l2->val) {temp->next = l2;l2 = l2->next;} else {temp->next = l1;l1 = l1->next;}temp = temp->next;}return returnList->next;}};
方法一：简单的递归，首先判断两个传过来的节点是不是空节点，如果是就直接返回另一个节点就行了。若都非空，就对其节点值进行判断，如果l1的值大于l2，因为要返回递增链表，那么肯定插入那个值较小节点的后边即l2，该节点已经被返回了，那么传入下一个该递归函数的节点就应该是l1和下一个节点了，反之，思路同上。
方法二：迭代，没啥好说的。
剑指 Offer 26. 树的子结构
/*** Definition for a binary tree node.* struct TreeNode {*int val;*TreeNode *left;*TreeNode *right;*TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/class Solution {public:bool isSubStructure(TreeNode* A, TreeNode* B) {// 特判：树 A 为空或树 B 为空时，直接返回 falseif (A == nullptr || B == nullptr) {return false;}/* 1. 判断 B 是 A 的子树，recur(A, B);2. 判断 B 是 A 的左子树，isSubisSubStructure(A->left, B);3. 判断 B 是 A 的右子树，isSubisSubStructure(A->right, B);*/return recur(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);}/*判断B是不是A的子树当节点 B 为空：说明树 B 已完成匹配，返回 true当节点 A 为空：说明树 A 全部遍历完也无法匹配树 B，返回 false当节点 A 和 B 的值不等：匹配失败，返回 false*/bool recur(TreeNode* A, TreeNode* B) {if (B == nullptr) {return true;}if (A == nullptr || A->val != B->val) {return false;}return recur(A->left, B->left) && recur(A->right, B->right);}};
这种递归题写起来还是很菜，不看人家题解虽然有思路但是根本写不出来。其实这个题就是两步，第一步找到A和B的相同节点，第二步就是通过相同节点对其左右子树进行判断，一直传递 A左B左和 A右B右进行递归判断就行了。当B完了就说明是子树，A完了，或者值不同了就说明不是子树了。
剑指 Offer 27. 二叉树的镜像
//方法一：/*** Definition for a binary tree node.* struct TreeNode {*int val;*TreeNode *left;*TreeNode *right;*TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/class Solution {public:TreeNode* mirrorTree(TreeNode* root) {if (!root) {return NULL;}TreeNode *temp = root->left;root->left = root->right;root->right = temp;mirrorTree(root->left);mirrorTree(root->right);return root;}};//方法二：class Solution {public:TreeNode* mirrorTree(TreeNode* root) {stack myStack;TreeNode *temp;myStack.push(root);while (!myStack.empty()) {temp = myStack.top();myStack.pop();if (!temp) {continue;}swap(temp->left, temp->right);if (temp->left) {myStack.push(temp->left);}if (temp->right) {myStack.push(temp->right);}}return root;}};//方法三：class Solution {public:TreeNode* mirrorTree(TreeNode* root) {queue myQueue;TreeNode *temp;myQueue.push(root);while (!myQueue.empty()) {temp = myQueue.front();myQueue.pop();if (!temp) {continue;}swap(temp->left, temp->right);if (temp->left) {myQueue.push(temp->left);}if (temp->right) {myQueue.push(temp->right);}}return root;}};
方法一：递归，交换左右节点就行。

普通版 剑指 Offer 浅刷浅刷( 六 )

普通版剑指 Offer 浅刷浅刷( 六 )