二叉树+树的OJ题讲解

求第K层节点个数

思路:走到K==1就不走了,一次传回得到的值

#include<stdio.h>
#include<stdlib.h>
//树的定义
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;//手搓一棵树 malloc
BTNode* BuyNode(int x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail");return;}node->data = x;node->left = node->right = NULL;
}BTNode* CreatBinaryTree()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);//怎么指向根据树写出来node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;return node1;
}//求第K层节点个数
int TreeLevelSize(BTNode* root, int k)
{if (root == NULL)return NULL;if (k == 1)return 1;//到K==1层就返回程序return TreeLevelSize(root->left, k - 1) + TreeLevelSize(root->right, k - 1);//其实一遍一遍的递归也算是--K了
}
int main()
{BTNode* root = CreatBinaryTree();printf("%d", TreeLevelSize(root,3));return 0;
}

二叉树查找值为X的节点

根据提示自己写的

BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;//该函数有返回值类型,是空也要返回空,不能直接写逗号if (root->data == x)return root;BTNode* ret1 = TreeFind(root->left, x);BTNode* ret2 = TreeFind(root->right, x);if (root->left == x)return ret1;if (root->right == x)return ret2;return NULL;//根左右都没有,返回空
}
int main()
{BTNode* root = CreatBinaryTree();TreeFind(root,4);return 0;
}

根本运行不出来

BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root->data == x)return root;BTNode* ret1 =NULL;BTNode* ret2 = NULL;if (root->left == x){ret1 = root->left;return ret1;}if (root->right == x){ret2 = root->right;return ret2;}return NULL;//这样应该每个情况都有返回值
}int main()
{BTNode* root = CreatBinaryTree();TreeFind(root,4);return 0;
}

第二种也是错的

判断条件值的类型是不对应的

查找的正确写法

BTNode* TreeFind(BTNode* root, BTDataType x)
{/*首先每一种状态必须要有返回值必须要有变量接收递归的值判断条件只要ret1 ret2不为空那就说明有与x相等的,直接判断ret就行就不会涉及root->left与x比较,而是root->data与x比较*/if (root == NULL)return NULL;if (root->data == x)return root;BTNode* ret1 = TreeFind(root->left, x);BTNode* ret2 = TreeFind(root->right, x);if (ret1)return ret1;//左子树有就不用再看右子树了,直接返回if (ret2)return ret2;return NULL;//左右都没有
}

leetcode 100.相同的树(简单)

思路:根和根比较,左子树和左子树比,右子树和右子树比

比较相同,一个相同没用,必须全部相同,返回什么?太难写了
反过来写:把所有的不相等的情况写出来返回false 走到光标闪动的位置就是全都相等

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
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);//都不返回错误//那就是相同的树了return true;
}

nice哦,逻辑能梳理清楚了

leetcode 101. 对称二叉树(和第一题类似)

思路:根和根比,左子树和右子树比,右子树和左子树比

错误写法:

bool _isSymmetric(struct TreeNode*left, struct TreeNode*right)
{//用来判断不等吧,相等返回值不好写if(left==NULL&&right==NULL)return true;if(left==NULL||right==NULL)return false;//都有值了,判断值if(left!=right)return false;return _isSymmetric(left,right)&& _isSymmetric(right,left);//左右 右左都要比return true;
}
bool isSymmetric(struct TreeNode* root) 
{return _isSymmetric(root->left,root->right);}

这个测试用例过不了

是因为我只是传了左右节点而不是左右子树
到了节点2,我比较的是3,4 而不是3 和 3 还是要传根节点的左右子树

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
//再写一个函数 一般在前面+横杠
bool _isSymmetric(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 _isSymmetric(p->left,q->right)&&_isSymmetric(p->right,q->left);return true;/*if(p->right==NULL||q->left==NULL)return false;//都有值了,判断值if(p->left!=q->right||p->right!=q->left)return false;return _isSymmetric(p->left,q->right)&& _isSymmetric(p->right,q->left);//左右 右左都要比return true;*/
//}
bool isSymmetric(struct TreeNode* root) 
{return _isSymmetric(root->left,root->right);}

思路得清晰,判断完值之后后面就是重复的判断子树,直接递归了,不要做多余的判断,后面的操作相同

144.二叉树的前序遍历并存到数组里(数组自己malloc出来)

我们该扩容多大的数组?—>把树遍历一遍求个数

 int TreeSize(struct TreeNode*root){return root==NULL?0:TreeSize(root->left)+TreeSize(root->right)+1;//左子树节点个数+右子树节点个数+根}void preorder(struct TreeNode*root,int*a,int *pi){if(root==NULL)return;a[(*pi)++]=root->val;preorder(root->left,a,pi);preorder(root->right,a,pi);}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {*returnSize=TreeSize(root);int*a=(int*)malloc(sizeof(int)*(*returnSize));int i=0;preorder(root,a,&i);return a;
}

其中returnsize是第一次接触的输出型参数

力扣中要返回数组就是要返回数组大小

为什么不传i而是传指针pi

因为i在形参是局部变量是并没有因为递归而累加(实际改变的)所以要改成传址调用