链式二叉树oj题

1.输入k ，找第k层节点个数

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);
}

在这里我们要确定递归子问题，第一个就是NULL时返回，还有一个就是k=1时就是我们要找的层数。

2.输入一个数，查找该数，找到了返回其地址。

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;
}

在这里我们需要弄明白的是，在某个开辟的栈帧中找到了该数据，直接返回其指针，是得不到它的地址的。

3.判断两棵树是相同的

bool isSametree(BTNode* root1, BTNode* root2) {//都为空if (root1 == NULL && root2 == NULL) {return true;}//其中一个为空if (root1 == NULL || root2 == NULL) {return false;}if (root1->val != root2->val) {//判断值是否相同return false;}return isSametree(root1->left, root2->left) &&isSametree(root1->right, root2->right);
}

4.判断是否为镜像/对称二叉树，也就是左右子树是否相同

bool _isSymmetric(BTNode* root1, BTNode* root2) {//根比较//左子树和右子树比较//右子树和左子树比较//都为空if (root1 == NULL && root2 == NULL) {return true;}//一个为空一个不为空if (root1 == NULL || root2 == NULL) {//短路求值return false;}if (root1->val != root2->val) {return false;}return _isSymmetric(root1->left, root2->right) &&_isSymmetric(root1->right, root2->left);
}
bool isSymmetri(BTNode* root) {return _isSymmetric(root->left, root->right);//将根的两个子树传递给子函数
}

5.在一棵树上找另一棵树

bool issubTree(BTNode* root, BTNode* subroot) {if (root == NULL)return false;if (root->val == subroot->val&& isSametree(root, subroot)) {//当遍历时发现根相同时才开始遍历比较//为了防止不止一处地方根相同且有一处根相同的地方并不完全相等，所以我们需要这两个条件同时成立才返回true.return true;}//遍历return issubTree(root->left,subroot) || issubTree(root->right,subroot);
}

这里与其他函数结合可以更好地解决问题。