php企业网站开发方案,网站建站网站设计,百度信息流推广平台,网站建设而上回我们手撕了一棵二叉树,并且通过递归完成了遍历,这回我们将深入理解用递归解决相关的二叉树问题,数量使用分治的思想.
上回的代码:
#includestdio.h
#includestdlib.h
typedef struct BinTreeNode
{struct BinTreeNode* left;struct BinTreeNode* right;i…上回我们手撕了一棵二叉树,并且通过递归完成了遍历,这回我们将深入理解用递归解决相关的二叉树问题,数量使用分治的思想.
上回的代码:
#includestdio.h
#includestdlib.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的节点加1NULL则直接返回然后左右节点的返回值比较最后返回大的值。
代码如下
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(rootNULL)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);
}这题思路和上题也大差不差,我把递归内容拉出来了而已 希望这篇学习之后大家能学会这种分治的思想谢谢阅读。
