学步园

一、判断一个二叉树A中是否包含另外一棵二叉树B

思路：首先在A中找到与B的根节点值一样的节点R，然后判断A中以R为根节点的子树是不是包含二叉树B。

bool ifContains(BinaryTreeNode * treeA,BinaryTreeNode * treeB){
    bool result = false;
    if(treeB == NULL)
      result = true;
    if(treeA != NULL && treeB != NULL){
        if(treeA -> value == treeB -> value)
            result = isSubTree(treeA,treeB);
        if(!result)
            result = ifContains(treeA -> left,treeB);
        if(!result)
            result = ifContains(treeA -> right,treeB);
    }
    return result;
}
bool isSubTree(BinaryTreeNode * treeA,BinaryTreeNode * treeB){
    if(treeB == NULL)
        return true;
    if(treeA == NULL || treeA -> value != treeB -> value)
        return false;
    return isSubTree(treeA -> left,treeB -> left) && isSubTree(treeA -> right,treeB -> right);
}

二、二叉树的镜像

思路：前序遍历一棵树的每个节点，如果遍历到的节点有子节点，就交换它的两个子节点，当交换完所有非叶子节点的左右节点后，就得到树的镜像。

代码：

void * Mirror(BinaryTreeNode * pRoot){
    //这里判断一下左右子节点是不是同时为空，可以提高效率
    if((pRoot == NULL) || (pRoot -> left == NULL && pRoot -> right == NULL))
        return;
    BinaryTreeNode * pLeft = pRoot -> left;
    BinaryTreeNode * pRight = pRoot -> right;
    BinaryTreeNode * ptemp = pRoot -> left;
    pLeft = pRight;
    pRight = ptemp;

    if(pRoot -> left != NULL)
        Mirror(pRoot -> left);
    if(pRoot -> right != NULL)
        Mirror(pRoot -> right);
}

三、二叉树的深度

利用前序遍历的方法实现：

int BinaryTreeDepth(BTN * pRoot){
  if(pRoot == NULL)
    return 0;
  int leftDepth = BinaryTreeDepth(pRoot -> left);
  int rightDepth = BinaryTreeDepth(pRoot -> right);
  return (leftDepth > rightDepth)?(leftDepth + 1):(rightDepth + 1);
}

引申：输入一颗二叉树的根结点，判断该树是不是平衡二叉树，如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是平衡二叉树。

方法一：根据刚才求二叉树深度的函数求出每个结点的左右子树的深度，然后判断是不是平衡二叉树，如果每个结点都是，那么整个树就是。

bool isBalanceTree(BTN * pRoot){
  if(pRoot == NULL)
    return true;
  int leftDepth = BinaryTreeDepth(pRoot -> left);
  int rightDepth = BinaryTreeDepth(pRoot -> right);
  if(leftDepth - rightDepth > 1 || leftDepth - rightDepth < -1)
    return false;
  return isBalanceTree(pRoot -> left)&&isBalanceTree(pRoot -> right);
}

方法二：上面的方法有很大的弊端，那就是时间复杂度太大，结点越靠近叶子结点，它被重复遍历的次数越多。

//这个函数其实要给掉用它的函数返回两个值，一是以这个结点为根结点的树是否是平衡二叉树，
//二是以该结点为根结点的树的深度是多少，因此我们需要定义一个int型的变量作为参数让它进入函数体得到
//二叉树的深度
bool isBalanceTree(BTN * pRoot,int * depth){
  if(pRoot == NULL){
    *depth = 0;
    return true;
  }
  int depthOfLeft;
  int depthOfRight;
  int depthDiff;
  if(isBalanceTree(pRoot -> left,&depthOfLeft) && isBalanceTree(pRoot -> right),&depthOfRight){
    depthDiff = depthOfLeft - depthOfRight;
    if(depthDiff < -1 || depthDiff > 1)
      return false;
    *depth = (depthOfLeft > depthOfRight)?(depthOfLeft + 1):(depthOfRight + 1);
    return true;
  }
  return false;
}
bool isBalanceTree(BTN * pRoot){
  int depth = 0;
  return isBalanceTree(pRoot,&depth);
}

后来又写的一份代码:

bool isBalanceTree(BiNode * root,int &depth){
	if(root == NULL){
		depth = 0;
		return true;
	}
	int leftDepth;
	int rightDepth;
	int diffDepth;
	bool isLeft = isBalanceTree(root ->lchild,leftDepth);
	bool isRight = isBalanceTree(root ->rchild,rightDepth);
	depth = leftDepth >= rightDepth ? leftDepth+1 : rightDepth+1;
	diffDepth = leftDepth - rightDepth;
	if(diffDepth > 1 || diffDepth < -1)
		return false;
	return isLeft && isRight;
}

bool isBalanceTree(BiNode * root){
	int depth;
	return isBalanceTree(root,depth);
}

四、求二叉树第k层有多少个节点

这个问题不要这么想，我先知道第k-1层有多少个节点，然后看第k-1层节点的左右分支有多少不为null，这个问题要用递归的方式实现：

求以root为根的二叉树第k层有多少个节点相当于求以root->lchild为根的二叉树第k-1层的节点数与以root->rchild为根的二叉树第k-1层的节点数之和。

1.当root为null时，节点数为0；

2.当root不为null时，求第k层节点个数：

   k == 1，节点数为1；

   k > 1，这个要递归；

   k < 1，节点数为0；

int numOfKthLevel(BiNode * root,int k){
	if(root == NULL || k < 1)
		return 0;
	if(k == 1)
		return 1;
	return numOfKthLevel(root ->lchild,k-1) + numOfKthLevel(root ->rchild,k-1);
}

五、根据一个数组构建一个搜索二叉树

BiNode* createBiTreeByArray(int nodeValues[],int length){
	if(length <= 0)
		return NULL;
	BiNode * root = NULL;
	for(int i = 0; i < length; i++){
		root = insertNode(root,nodeValues[i]);
	}
	return root;
}
//这个函数的作用是将value插入root为根结点的搜索二叉树中，并将根节点返回
BiNode* insertNode(BiNode * root,int value){
	BiNode* node;
	if(!(node = (BiNode*)malloc(sizeof(BiNode))))
		return NULL;
	node ->data = value;
	node ->lchild = NULL;
	node ->rchild = NULL;
	if(root == NULL)
		return node;
	if(root ->data > value)
		//这里很重要，我们将root->lchild看成根，将value插入以root->lchild为根结点的搜索二叉树中，并将root->lchild返回重新链接到root上
		root->lchild = insertNode(root->lchild,value);
	else
		root ->rchild = insertNode(root ->rchild,value);
	return root;
}

六、求二叉树中节点的最大距离
即二叉树中相距最远的两个节点之间的距离。
递归解法：
（1）如果二叉树为空，返回0，同时记录左子树和右子树的深度，都为0
（2）如果二叉树不为空，最大距离要么是左子树中的最大距离，要么是右子树中的最大距离，要么是左子树节点中到根节点的最大距离+右子树节点中到根节点的最大距离，同时记录左子树和右子树节点中到根节点的最大距离。

int max(int first,int second){
	return (first >= second) ? first:second;
}

//maxLeft是root左子树的高度，maxRight是root右子树的高度
int getMaxDistance(BiNode * root,int & leftHeight,int & rightHeight){
	if(root == NULL){
		leftHeight = 0;
		rightHeight = 0;
		return 0;
	}

	int maxDistance;
	int leftMaxDistance,rightMaxDistance;
	int llHeight,lrHeight,rlHeight,rrHeight;
	if(root ->lchild == NULL){
		leftHeight = 0;
		leftMaxDistance = 0;
	}
	else{
		leftMaxDistance = getMaxDistance(root ->lchild,llHeight,lrHeight);
		leftHeight = max(llHeight,lrHeight) + 1;
	}
	if(root ->rchild == NULL){
		rightHeight = 0;
		rightMaxDistance = 0;
	}else{
		rightMaxDistance = getMaxDistance(root ->rchild,rlHeight,rrHeight);
		rightHeight = max(rlHeight,rrHeight) + 1;
	}

	maxDistance = max(max(leftMaxDistance,rightMaxDistance),leftHeight+rightHeight);
	return maxDistance;
}

自己写的另外一种方法，但是不太好，因为返回值是以root为根节点的树的高度，最大距离作为参数放在函数头中

int maxDistance(BiNode * root,int & maxDis){
	if(root == NULL){
		maxDis = 0;
		return 0;
	}
	int maxDisLeft,maxDisRight,leftHeight,rightHeight,height;
	leftHeight = maxDistance(root ->lchild,maxDisLeft);
	rightHeight = maxDistance(root ->rchild,maxDisRight);
	height = leftHeight >= rightHeight ? leftHeight + 1 : rightHeight + 1;
	maxDis = maxDisLeft >= maxDisRight ? maxDisLeft : maxDisRight;
	maxDis = maxDis >= (leftHeight + rightHeight) ? maxDis : (leftHeight + rightHeight);
	return height;
}