二叉树的分治

分治和遍历 他们 虽然都是遍历一遍二叉树，但是遍历在某些时候解决不了问题
更倾向于分治

三种二叉树递归境界

看山还是山
看山不是山 懂得递归的子过程
看山还是山 不要想递归的子过程，就当成完整的子问题

前中后序遍历

// 二叉树节点个数
int BinaryTreeSize(BTNode* root);

更加倾向于分而治之 ，根本身自己的1个+左子树的个数+右子树的个数

int TreeSize(BTNode* root)//分而治之
{if (root == NULL){return 0;}return TreeSize(root->left) + TreeSize(root->right) + 1;
}//void TreeSize(BTNode* root, int* n)//遍历
//{
//	if (root == NULL)
//	{
//		return;
//	}
//	++(*n);
//	TreeSize(root->left, n);
//	TreeSize(root->right, n);
//}

二叉树的高度
当前树高度=左右子树高度大的＋1

这种用遍历就很难搞阿

int TreeHeight(BTNode* root)
{if (root == NULL){return 0;}int leftheight = TreeHeight(root->left);int rightheight = TreeHeight(root->right);return leftheight > rightheight ? leftheight + 1 : rightheight + 1;
}

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
当前树的第K层节点数=·左子树的第K-1层个数＋右子树的第K-1层个数

int TreeKLevel(BTNode* root, int k)
{if (root == NULL)return 0;if (k == 1)return 1;return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);
}

但是如果递归层次过深就会栈溢出

二叉树的后序

下列三种是一种后序遍历，访问根结点的操作发生在遍历其左右子树之后

求二叉树高度
先递归左子树，再右子树，左子树右子树都完了最后返回高度高的+1

int TreeHeight(BTNode* root)
{if (root == NULL){return 0;}int leftheight = TreeHeight(root->left);int rightheight = TreeHeight(root->right);return leftheight > rightheight ? leftheight + 1 : rightheight + 1;
}

求二叉树节点个数

int TreeSize(BTNode* root)//分而治之
{if (root == NULL){return 0;}return TreeSize(root->left) + TreeSize(root->right) + 1;
}

归并排序
递归左子树有序，递归右子树有序，最后 [begin1,end1] [begin2,end2] 归并排序

快排是一种前序

先选出一个keyi 再递归左子树 再右子树