[数据结构]二叉树与递归OJ

上回我们手撕了一棵二叉树,并且通过递归完成了遍历,这回我们将深入理解用递归解决相关的二叉树问题,数量使用分治的思想.

上回的代码:

#include<stdio.h>
#include<stdlib.h>
typedef struct BinTreeNode
{
	struct BinTreeNode* left;
	struct BinTreeNode* right;
	int val;
}BTNode;
BTNode* BuyBTNode(int val)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->val = val;
	newnode->left = NULL;
	newnode->right = NULL;
	return newnode;
}
BTNode* CreateTree()
{
	BTNode* n1 = BuyBTNode(1);
	BTNode* n2 = BuyBTNode(2);
	BTNode* n3 = BuyBTNode(3);
	BTNode* n4 = BuyBTNode(4);
	BTNode* n5 = BuyBTNode(5);
	BTNode* n6 = BuyBTNode(6);

	n1->left = n2;
	n1->right = n4;
	n2->left = n3;
	n4->left = n5;
	n4->right = n6;

	return n1;
}
void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	printf("%d ", root->val);
	PreOrder(root->left);
	PreOrder(root->right);
}

void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	InOrder(root->left);
	printf("%d ", root->val);
	InOrder(root->right);
}
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->val);
}



int main()
{
	BTNode* root = CreateTree();
	printf("前序遍历:");
	PreOrder(root);
	printf("\n");

	printf("中序遍历:");
	InOrder(root);
	printf("\n");

	printf("后序遍历:");
	PostOrder(root);
	printf("\n");

	return 0;
}

一、求二叉树存储的元素个数

这里我的思路很简单，我们可以通过递归将二叉树向左右孩子遍历，不为空则加1.

代码如下：

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

二、二叉树的最大深度

这个思路整体也不难，我们一样用递归左右孩子节点，每通过一个非0的节点加1，NULL则直接返回，然后左右节点的返回值比较，最后返回大的值。

代码如下：

int maxDepth(BTNode* root)
{
	if (root == NULL)
		return 0;
	int leftDepth = maxDepth(root->left);
	int rightDepth = maxDepth(root->right);

	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

三、寻找X的所在的节点

这个就是在左右递归上加上判断val是否等于X

代码示例：

BTNode* TreeFind(BTNode* root, int x)
{
	if (root == NULL)
		return NULL;

	if (root->val == x)
		return root;

	BTNode* ret1 = TreeFind(root->left, x);
	if (ret1)
		return ret1;

	BTNode* ret2 = TreeFind(root->right, x);
	if (ret2)
		return ret2;

	return NULL;
}

四、单值二叉树

965. 单值二叉树 - 力扣（LeetCode）

bool isUnivalTree(struct TreeNode* root) {
    if(root==NULL)
    return true;
    if (root->left) 
    {
        if (root->val != root->left->val || !isUnivalTree(root->left)) 
        {
            return false;
        }
    }
    if (root->right) 
    {
        if (root->val != root->right->val || !isUnivalTree(root->right)) 
        {
            return false;
        }
    }
    return true;
}

运用递归判断只要存在一个false最后结果必然false

五、相同的树

100. 相同的树 - 力扣（LeetCode）

bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
{
    if(p == NULL && q == NULL)
        return true;

    if(p == NULL || q == NULL)
        return false;
    
    if(p->val != q->val)
        return false;

    return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}

这题思路和上题差不多,排除特殊情况就行。

六、对称二叉树

101. 对称二叉树 - 力扣（LeetCode）

bool judge(struct TreeNode *p ,struct TreeNode *q){
    if(p == NULL && q == NULL){
        return true;
    }
    else if(p == NULL || q == NULL){
        return false;
    }
    else if(p -> val != q -> val){
        return false;
    }
    return judge(p -> left,q -> right) && judge(p -> right,q -> left);
}
bool isSymmetric(struct TreeNode* root){
    return judge(root -> left,root -> right);
}

这题思路和上题也大差不差,我把递归内容拉出来了而已

---

希望这篇学习之后，大家能学会这种分治的思想，谢谢阅读。