微信做引流网站,微信里面如何做网站,昆明网站制作在线,公司网站域名如何建立目录
#x1f341;一、二叉树的销毁
#x1f341;二、在二叉树中查找某个数#xff0c;并返回该结点
#x1f341;三、LeetCode——检查两棵二叉树是否相等
#x1f315;#xff08;一#xff09;、题目链接#xff1a;100. 相同的树 - 力扣#xff08;LeetCode一、二叉树的销毁
二、在二叉树中查找某个数并返回该结点
三、LeetCode——检查两棵二叉树是否相等
一、题目链接100. 相同的树 - 力扣LeetCode
二、解答
四、LeetCode——二叉树的前序遍历与上一篇文章不太一样
一、题目链接144. 二叉树的前序遍历 - 力扣LeetCode
二、解答 接上篇文章我们接着学习关于链式二叉树的几种操作。 一、二叉树的销毁 //销毁
void FreeDestroy(BTNode* root)
{if (root NULL){return;}FreeDestroy(root-left);FreeDestroy(root-right);free(root);
}对于销毁使用前序或者后序遍历都可以但前序需要在销毁根结点的之前用临时指针保存根节点的左右子树这样比较麻烦所以最合适的还是后序先销毁左右子树然后才销毁根节点这样按顺序的来就可以了。而我们使用递归最重要的是如何转换为子问题以及最小子递归的返回条件问题这里很显然我们访问到NULL时就可以返回了然后在依次销毁。 二、在二叉树中查找某个数并返回该结点 //在二叉树中找某个数的结点
BTNode* TreeFind(BTNode* root,int x)
{if (root NULL)return NULL;if (root-val x)return root;BTNode* tmp TreeFind(root-left, x);if (tmp)return tmp;tmp TreeFind(root-right, x);if (tmp)return tmp;return NULL;
}①依然是遍历的思路这里我们选择前序遍历先将根节点比较了再去左右子树比较 ②然后最小子递归返回条件也是当root为空时返回NULL表示该条路径中没有找到数x ③若当前结点的数据等于x表示找到了就返回该结点 ④若没找到就先去左子树找若左子树返回值不为NULL说明找到了返回左孩子结点若左子树没找到则返回NULL不进如if语句 ⑤左子树没找到就开始找右子树和左子树同样的道理找到返回右子树结点没找到返回NULL 三、LeetCode——检查两棵二叉树是否相等
一、题目链接100. 相同的树 - 力扣LeetCode 二、解答 bool isSameTree(struct TreeNode* p, struct TreeNode* q) {//两个树都为NULLif(pNULLqNULL)return true;//其中一个为NULLif(pNULL||qNULL)return false;//都不为NULL则比较数据if(p-val!q-val)//到这里说明该结点数据相同则比较左子树然后比较右子树return false;return isSameTree(p-left,q-left)isSameTree(p-right,q-right);
} ①若两棵树都为NULL则代表此结点的数据相同返回ture ②若其中一个为NULL另一个不为NULL则两结点数据不同返回false ③若两个都不为NULL则比较数据若数据不相同则两结点数据不同返回false ④若不为上述三种情况则说明该结点相同则比较其左子树然后比较其右子树 四、LeetCode——二叉树的前序遍历与上一篇文章不太一样
一、题目链接144. 二叉树的前序遍历 - 力扣LeetCode 二、解答 /*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
/*** Note: The returned array must be malloced, assume caller calls free().*///手动写的计算树的结点个数函数int TreeSize(struct TreeNode*root){return rootNULL?0:TreeSize(root-left)TreeSize(root-right)1;}//手动写的遍历函数
void preorder(struct TreeNode* root,int* a,int* pi)
{if(rootNULL)return;a[(*pi)]root-val;preorder(root-left,a,pi);preorder(root-right,a,pi);
}//LeetCode给定函数
int* preorderTraversal(struct TreeNode* root, int* returnSize) {int nTreeSize(root);int* a(int*)malloc(sizeof(int)*n);int j0;preorder(root,a,j);*returnSizen;return a;
} 二叉树的前序遍历我们在上一篇文章已经讲解了是一个很简单的过程但这道题不一样不一样在这里存在一些OJ题的技巧解释 ①这道题的意思是叫我们把树的前序遍历的结果存放在一个数组中最后在返回该数组的起始地址 ②我们看到LeetCode给定的函数接口中有两个形参一个是待操作的树另一个是整形指针但我们看整形指针字面意思应该知道我们应该返回一个数组的个数那为什么会是一个整形指针呢因为在接口外部传的是该变量地址我们要在函数接口中根据待测树的结点数去解引用整形指针改变函数外部的数组个数所以使用了传址调用。 ③所以我们手动写了一个函数计算出待测树的结点个数然后解引用returnSize将树的结点数赋值给它。 ④又因为我们要用到递归的思路所以又手动写了一个函数进行前序遍历及其将数据存到数组中的操作又因为数组需要用到下标为了下标j能在任意递归栈帧中改变所以我们使用了传址调用将下标j的地址传进去这样我们每赋值一次就解引用后加1这样下标就能动态改变 ⑤接着便是前序遍历的算法只是将打印换成了赋值给数组这一操作 本次知识到此结束希望对你有所帮助
