DS链式二叉树的基本操作和OJ题(12)

前言

  承接上篇，正文开始！

一、二叉树节点个数

  我相信肯多人第一反应想到静态局部变量或者全局变量来解决这个问题

int TreeSize(TreeNode* root)
{
	static int size = 0;
	if (root == NULL)
	{
		return 0;
	}

	++size;

	TreeSize(root->left);
	TreeSize(root->right);

	return size;
}

int size = 0;
void TreeSize(TreeNode* root)
{
	if (root == NULL)
		return;

	++size;

	TreeSize(root->left);
	TreeSize(root->right);
}

  无论是使用静态还是全局变量，使得生命周期不会受到函数栈帧销毁的影响，可以解决求节点个数的问题，这倒是对的，可这size生命周期也太长了，静态还是全局变量只能被定义一次，这就意味着第一次计算出来的结果是正确的，那么第二次的结果会延用上一次变量存储的值，不会清空重新计数，第二次就错了

这里使用分治思想，可以将求整课树节点个数分为求左右子树节点个数加上根节点之和，不断划分

int BinaryTreeSize(TreeNode* root)
{
    if (root == NULL) return 0;

    return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

二、二叉树叶子节点个数

  我们也可以看出，这里也是使用了分治的思想，求整棵树叶子节点个数之和分为求左右子树叶子节点个数

  三种情况：空节点返回0，不是空节点，属于叶子节点返回1，不是空节点也不是叶子节点，使用分治等于左右子树叶子之和

int BinaryTreeLeafSize(TreeNode* root)
{
    if (root == NULL) return 0;
    if (root->left == NULL && root->right == NULL) return 1;

    return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

三、二叉树的高度

这里也是使用了分治的思想，求整棵树高度分为求左右子树高度之间最大的高度再+1

瑕疵版本：

//由于TreeHeight(root->left) > TreeHeight(root->right) 的比较是不会记录结果
//需要高的那一份再次递归调用
//因此多次递归调用 TreeHeight(root->left) 和 TreeHeight(root->right)，造成重复计算
int TreeHeight(TreeNode* root)
{
	if (root == NULL) return 0;
	
	return TreeHeight(root->left) > TreeHeight(root->right) ?
		TreeHeight(root->left) + 1 : TreeHeight(root->right) + 1;
}

修正版本：

int TreeHeight(TreeNode* root) 
{
	if (root == NULL) return 0;

	int leftHeight = TreeHeight(root->left);
	int rightHeight = TreeHeight(root->right);

	return max(leftHeight, rightHeight) + 1;
}

四、二叉树第k层节点个数

第k层节点，就相当于是左右子树的 k - 1 层节点

int TreeLevelK(TreeNode* root, int k)
{
	assert(k > 0);
	if (root == NULL)
		return 0;

	if (k == 1)
		return 1;

	return TreeLevelK(root->left, k-1) + TreeLevelK(root->right, k-1);
}

五、二叉树查找值为x的节点

瑕疵版本：

TreeNode* TreeFind(TreeNode* root, BTDataType x)
{
	if (root == NULL) return NULL;
	if (root->data == x) return root;

	TreeFind(root->left, x);
	TreeFind(root->right, x);
    
	return NULL;
}

return 是return 上一层的，不是直接到最外层的

修正版本：

TreeNode* TreeFind(TreeNode* root, BTDataType x)
{
	if (root == NULL) return NULL;
	if (root->data == x) return root;

	TreeNode* ret1 = TreeFind(root->left, x);
	if (ret1) return ret1;
	TreeNode* ret2 =  TreeFind(root->right, x);
	if (ret2) return ret2;

	return NULL;
}

六、单值二叉树

力扣965.单值二叉树

bool isUnivalTree(TreeNode* root)
{
    if(root == NULL) return true;

    if(root->left && root->left->val != root->val)
        return false;
    if(root->right && root->right->val != root->val)
        return false;

    return isUnivalTree(root->left) && isUnivalTree(root->right);
}

六、相同的二叉树

力扣100.相同的树

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

七、二叉树的销毁

  后序遍历，因为肯定是要从后往前销毁的

void DestroyTree(TreeNode* root)
{
	if (!root) return;

	DestroyTree(root->left);
	DestroyTree(root->right);

	free(root);
	root = NULL;
}

八、翻转二叉树

力扣226.翻转二叉树

void _invertTree(struct TreeNode* root){
    if(root){
        struct TreeNode* tmp = root->left;
        root->left = root->right;
        root->right = tmp;
        _invertTree(root->left);
        _invertTree(root->right);
    }
}

struct TreeNode* invertTree(struct TreeNode* root){
    _invertTree(root);
    return root;
}

九、判断两棵树是否相同

力扣100.相同的树

bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
{
    if (!q && !p) return true;  //当两个节点都为空时，必为真
    if (!q || !p) return false; //当只有一个节点为空时候，必为假

    if (p->val != q->val) return false; //当相同位置的值不同时候，必为假

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

十、对称二叉树

力扣101.对称二叉树

class Solution {
public:
    bool _isSymmetric(TreeNode* root1, TreeNode* root2)
    {
        if (!root1 && !root2) return true;
        else if (!root1 || !root2) return false;

        if (root1->val != root2->val) return false;

        return _isSymmetric(root1->left, root2->right) && _isSymmetric(root1->right, root2->left);
    }

    bool isSymmetric(TreeNode* root)
    {
        return _isSymmetric(root->left, root->right);
    }
};

调皮一下，用一下Cpp代码
本题你可以思考一下何为对称，为什么要单独额外设置一个函数传两个节点指针

十一、平衡二叉树

力扣110.平衡二叉树

int maxDepth(struct TreeNode* root) {
    if (root == NULL) {
        return 0;
    }

    int LeftDepth = maxDepth(root->left);
    int RightDepth = maxDepth(root->right);

    return LeftDepth > RightDepth ? LeftDepth + 1 : RightDepth + 1;
}

bool isBalanced(struct TreeNode* root) {
    if (root == NULL) {
        return true;
    }

    int LeftDepth = maxDepth(root->left);
    int RightDepth = maxDepth(root->right);

    return abs(LeftDepth - RightDepth) < 2
        && isBalanced(root->left)
        && isBalanced(root->right);
}

方法是如果左右子树的高度差不超过1并且左右子树均为平衡二叉树则为平衡二叉树

十二、二叉树的子树

力扣572.另一棵树的子树

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) 
    {
        if (!p && !q){
            return true;
        }    
        else if ((p && !q) || (!p && q)){
            return false;
        }

        if (p->val != q->val){
            return false;
        }

        bool left = isSameTree(p->left, q->left);
        bool right = isSameTree(p->right, q->right);

        return left && right;  
    }

    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if (!root) return false;
        if (isSameTree(root, subRoot)) return true;

        bool isLeft = isSubtree(root->left, subRoot);
        bool isRight = isSubtree(root->right, subRoot);

        return isLeft || isRight;
    }
};

又用了Cpp代码，其实也很好理解，先看下右根节点引出的树是否与子树相同，若相同直接返回true；若不相同，则判断下左右子树是否相同，就这样一直递归下去

十三、二叉树的深度遍历

  将二叉树的数值通过遍历存储到一个新的数组中，与前文不同的是，我们不只是打印数值，而是存储，这就是深度遍历，大家可以自行尝试一下：
力扣144.二叉树的前序遍历
力扣94.二叉树的中序遍历
力扣145.二叉树的后序遍历

十四、一道较难的综合题

  你是否对二叉树有所掌握了呢？来试试这道题吧！
牛客网KY11.二叉树遍历

总结

  这篇写的好痛苦~给个赞吧！