9.7算法复习

链表奇偶排列：

用两个指针为奇结点，偶结点，在迭代中，奇结点下一个是此时偶节点下一个，然后再让偶节点下一个是更新后的奇结点下一个，如此往复，偶节点总是在一轮迭代后的后面，迭代完后就会得到一个奇结点链表和一个偶节点链表，再把头接到尾

链表去重：

检测当下结点与下个结点的值是否相同，同的话next更新为next->next，直到不同，那么当下结点的下一个就不是重复结点了

while(cur->next!=nullptr&&cur->next->next!=nullptr){
if(cur->val==cur->next->val){
cur->next=cur->next->next;}
else{
cur=cur->next;}
}

如果重的都不要，那就要用cur->next试探，2如果cur->next->next值同，那就要去重，去重就是cur此时在重的前一位，要让cur->next越过所以重复区域，用一个值记录当前重复的数，如果cur->next的值为这个重复的数，那就不断向后更新cur->next，直到cur->next越过当前这片重复区域

越过后也不一定就不是另一片重复区域，所以越过完后不要直接更新cur,而是让更新到下一片区域的cur->next继续检查cur->next->next是不是重复结点，即向后的更新cur=cur->next是在else里

while (cur->next != nullptr && cur->next->next != nullptr) {
	if (cur->next->val == cur->next->next->val) {
		int temp = cur->next->val;
		while (cur->next != nullptr && cur->next->val == temp) {
			cur->next = cur->next->next;
		}
	}
	else {
		cur = cur->next;
	}
}

二分查找：

迭代终止条件左指针小于等于右指针，然后在迭代中设置每轮的中指针，如果中指针所指值和目标值同，则直接返回。如果大于，则说明在左边，让r=m-1;不然，则在右边，l=m+1;然后进入下一轮迭代。

二维查找：

从左下角开始往右上选

如果比行头小，那么一定不在这行，r--;

如果比当前行头大(那么一定也比之上的所有行头大），则可能在这行

如果这行的这列比目标值小（也就说明以上的所有行列都比目标值小，排除掉），就往这行后面走，c++，直到在这行遇到目标值或遇到一个大的数；

如果比此时的行的此时列小，那就排除了这行这列后的所有列，那就要r--,在这一列的基础上行往上走走，此时又要检测这时的行与目标值的关系，即进入到了下一轮迭代

while (r >= 0 && c <= cmax) {
	while (mar[r][c] > target) {
		r--;
	}
	if (mar[r][c] == target) {
		return;
	}
	while (mar[r][c] < target) {
		c++;
	}
	if (mar[r][r] == target) {
		return;
	}
	//一轮循环内走行与列
}
for (int i = n - 1, j = 0; i >= 0 && j < m;) {
	if (array[i][j] > target) {
		i--;
	}
	else if (array[i][j] < target) {
		j++;
	}
	else {
		return true;
	}
}

寻找峰值

左右指针夹，

迭代：左右指针重合

左指针：如果下一个比当前大，则左指针到位

右指针：如果前一个比当前大，则右指针到位

最后检查一下左指针下一个和右指针上一个是不是一个数，是的话返回，

不是的话，说明这是两个可能的峰头，这时舍弃左指针的峰头，让左指针++，直到遇到左右架上一个峰头

求二叉树最大深度

递归之分治法

解决问题，每次递归定向缩小问题规模，用变量接受缩小后的问题的结果，用于解决当下规模的情况

关键在于，1如何缩小问题规模，最小规模是什么？

2.如何处理规模变小后的问题的结果，即为什么要缩小问题规模，缩小后的处理完了之后怎么做

即怎么再合并在一起

怎么分（缩小问题规模），怎么合（如何合并子问题的结果）

划分子问题：

如果我要求整个树的高度，我就要知道左右子树的高度（即将整个树的规模，向下划分为左右子树），接着就是递归，如果我要知道左右子树的高度，就要知道子树的左右子树高度……

直到叶子结点之后的空结点，才返回高度为0（子问题的最小规模）

合并子问题答案：

如果我知道了左右子树的高度，就取其最大值，再加1（根节点一层），就是这颗树的高度

二叉树中和为某一值

递归之状态转移

在每个结点有不同的选择进入不同的状态（结点），可以选择做或不做，向左还是向右，无论结果如何，其都是由当下的结点所引出的

在不断的状态转移中，没有到达的状态越来越少，最终遍历完，走到末路，判断出结果。

此时就要往回推，判断出之前的结点（能抵达末路结点）的最终结果有哪些，越往上对应的可能性越多，越细分可能性越少，所以在向下递归（做状态转移）时，要用||（或）来并接多种的状态转移（选择），而不是绑定到唯一的选择上

二叉搜索树转为双向链表（中序遍历）

双向链表有前驱和后继指针

在遍历过程中，各结点的地址没有发生变化，是pre不断变化，且相当于在链表中做线性向后移动

首先pre初始为nullptr,在递归遍历时，第一次停止向下递归，开始做操作时，需要判断pre=nullptr，做初始化，让头结点和前驱pre结点都指向这个结点，因为这个结点就是双向链表的第一个结点，之后，就是回递归途中，不断对结点做操作，为让前驱结点的后继为当下结点，让当下结点的前驱为前驱结点，之后再让前驱指针指向当下结点，完成一次对递归结点的操作，回到上层递归。

即，递归方法决定遍历结点的顺序，其中操作由双向链表的建立决定，即该怎么干怎么干

对称的二叉树

二叉树对称，即左子树和右子树镜像对称

子问题的划分：

如果要让整个二叉树对称，就必须左右子树都对称，而要左右子树都对称，可分为两部分，一是镜像位置的左右子树值相同，二是这个位置下面的子树镜像位置也对称，接着向下就是子树的左右子树都对称……直到到叶子结点，向下没有分支

子问题结果的合并：

首先是要镜像位置向下的左右子树都（&&）对称（递归部分），然后是要镜像位置对称（非递归部分，比子问题多出来的部分)，即值相同

要判断镜像位置，就需要两个参数，一个向左，一个向右

bool isvalid(treenode* root1, treenode* root2) {
	if (root1 == nullptr && root2 == nullptr) { return true; }//子问题的最小规模
	if (root1->val != root2->val || root1 == nullptr || root2 == nullptr) {
		return false;//非递归部分，即比规模缩小的子问题多出来的部分(指左右子节点上的镜像根结点）
	}//过了就说明多出来的部分检验通过了，接下来是否成立取决于子问题是否成立
	return isvalid(root1->left, root2->right) && isvalid(root1->right, root2->left);//镜像位置下有两个子问题，且的关系
}

即将大问题经过分析转化为递归部分（子问题，与母问题等价，只是规模变小），非递归部分（相较于下一级的子问题多出来的部分，子问题内不包括）

子问题的最小规模就是只有非递归部分而没有递归部分，即只经过一次处理就解决了

合并二叉树

问题的划分：

1.合并根节点（比子问题多出来的部分）

2.合并左子树，合并右子树（与母问题本质相同的子问题）

子问题的最小规模就是向下没有子问题可以继续划分（即叶子结点）

treenode* merge(treenode* root1, treenode* root2) {
	if (root1 == nullptr) {
		return root2;
	}
	if (root2 == nullptr) {
		return root1;
	}
	treenode* res = new treenode(root1->val + root2->val);
	res->left = merge(root1->left, root2->left);
	res->right = merge(root1->right, root2->right);
	return res;
}

递归（分治法）解决问题：

1.分析问题本质，尝试缩小规模，以此来拆分出递归部分与非递归部分

2.解决非递归部分

3.解决递归部分

4.处理递归（子问题）的最小规模

具体递归方法代码顺序为423或432

镜像反转二叉树

问题的划分：

根节点不用反转

1.反转根节点的左右子树（非递归部分）

2.反转以左右子树为根节点的左右子树（本质相同的递归部分）

void reverse(treenode* root) {
    if(root==nullptr){return;}
	treenode* left = root->left;
	treenode* right = root->right;
	root->left = right;
	root->right = left;
	reverse(root->left);
	reverse(root->right);
}

或者

先2后1

treenode* reverse(treenode* root) {
	if (root == nullptr) { return nullptr; }
	treenode* left = reverse(root->left);
	treenode* right = reverse(root->right);
	root->left = right;
	root->right = left;
	return root;
}

反转意味着，让根的左儿子成为右儿子，右儿子成为左儿子

判断是不是二叉搜索树

问题的划分

非递归部分：根节点的左右结点满足特性

递归部分：以左右结点为根节点的左右结点都（&&）满足特性

最小规模：没有递归部分，即没有左右结点，即叶子节点

这里子问题与母问题并不完全独立，即非递归部分与递归部分相较于问题本身并非独立

bool isValidBST(TreeNode* root) {
    if (root == nullptr || (root->left == nullptr && root->right == nullptr)) {
        return true;
    }
    if (root->left == nullptr && root->right->val < root->val) {
        return false;
    }
    if (root->right == nullptr && root->left->val > root->val) {
        return false;
    }
    if (root->left->val > root->val || root->right->val < root->val) {
        return false;
    }
    return isValidBST(root->left) && isValidBST(root->right);
}
//这里顺序为先解决非递归部分，再解决递归部分
//存在问题，即左子树的右子树可能特别大，比根节点大
//这时，即使通过了递归，非递归的检查，也依然不是搜索树，这里却没办法判断
//那么，这个问题就不能先解决非递归部分，因为不仅需要判断根节点的左右
// 还需要保证左子树的都比根节点小，如果直接加为<root->val，而右子树也和其共用的一个方法
// 所以不能先解决非递归部分
// 进一步地，所谓搜索树，在中序遍历时是升序列
// 那么要保证左子树都比根节点小，就只需要保证根节点比上一个结点大就行
//而这上一个结点的递归层数并不能确定，但可以确定，是在中序序列里
//那么，就只能采用先解决递归部分的方法，因为只有这样，才能保证为中序序列
//即具体是要先解决那部分问题，要具体情况具体讨论分析
bool isvalid(treenode* root) {
    if (root == nullptr) {
        return true;
    }
    if (!isvalid(root->left)) {
        return false;
    }//解决递归部分
    if (pre->val > root->val) {
        return false;
    }//非递归部分
    pre = root;
    if (!isvalid(root->right)) {
        return false;
    }//递归部分
    return true;
}

判断是不是完全二叉树

判断逻辑：

层序遍历

每层第一次遇到空结点后，就不能再遇到非空结点，并且这层遍历完后就没有下一层。

queue<treenode*>q;
while (!q.empty()) {
	int num = q.size()//每层的结点数
	for (int i = 0; i < num; i++) {//从左到右遍历这层结点
		treenode* cur = q.front();
		q.pop();
		if (cur == nullptr) {
			flag = 1;
		}//if,else，每次循环只执行其中一个
		else {
			if (flag) {
				return false;
			}
			q.push(cur->left);
			q.push(cur->right);//由于是要判断是不是完全树，所以不需要排除空结点，排除了会出问题
		}
	}
}

判断是不是平衡二叉树

问题的划分：

非递归：根节点和左右结点满足平衡二叉树定义

递归：以左右结点为根节点的左右结点满足平衡二叉树定义

两部分完全独立

要解决递归部分，就是要解决最小规模子问题

只有处理了最小规模子问题，才能解决所有递归部分

int deeptree(treenode* root) {
	if (root == nullptr) {
		return 0;
	}
	return max(deeptree(root->left), deeptree(root->right)) + 1;
}
isbalance(treenode* root) {
	if (root == nullptr) {
		return true;
	}
	int deepleft = deeptree(root->left), deepright = deeptree(root->right);
	if (deepleft - deepright > 1 || deepright - deepleft > 1) {
		return false;
	}
	return isbalance(root->left) && isbalance(root->right);
}