【数据结构与算法】二叉树的综合运用--1https://developer.aliyun.com/article/1424484
二，判断单值二叉树
单值二叉树：二叉树的每个结点都具有相同的值。
分析：
我们可遍历二叉树，并且每一个节点值都和根节点的值进行比对，如果不等于根节点的值，则不是单值树。
代码如下：
/**以下是二叉树的结构式 * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ bool JudgeTree(struct TreeNode* root, int x) { if (!root) { return true; } if (root->val != x) { return false; } //当有一个不满足条件时，一直返回的是false，最终结果也是false return JudgeTree(root->left, x) && JudgeTree(root->right, x); } bool isUnivalTree(struct TreeNode* root) { if (!root) { return true; } return JudgeTree(root, root->val); }
举一反三：
当我们遇到像bool类型的二叉树算法时，可以像上述题型一样，系统给定函数的类型和参数与我们遍历思路不同时，可再创建一个返回类型和参数都令我们"满意的函数"。如以上题中系统给定的函数是bool isUnivalTree(struct TreeNode* root)，参数令我们不满意，我们可创建一个函数：bool JudgeTree(struct TreeNode* root, int x)，有个参数x以便后面我们比较。
还有，像bool类型的函数一般不好在其中递归遍历，所以，当递归遍历时经常在返回值中运用逻辑运算符连接遍历。如以上题中return JudgeTree(root->left, x) && JudgeTree(root->right, x)。在此函数中用"&&"符号连接进行遍历，而具体使用哪个要根据情况而定，这方面还是要多加练习。
三，求二叉树的最大深度
题解：二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。
分析：
显然，本题也需要我们运用二叉树基础算法中的遍历算法。求解最大深度，我们可在递归遍历时记录在此函数中，以root为根结点左右孩子的总共数量，大的一方就是以此函数中root为根结点的子二叉树的最大深度，即当最终返回时，返回的是二叉树的最大深度。
代码如下：
/** * 二叉树的结构 * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ int maxDepth(struct TreeNode* root){ if (!root) { return 0; } //记录左孩子的数量 int leftsize = maxDepth(root->left) + 1; //记录右孩子的数量 int rightsize = maxDepth(root->right) + 1; //返回以此递归函数中的子二叉树的最大深度 return (leftsize > rightsize) ? leftsize : rightsize; }
举一反三：
本题要明白的是像类似于int leftsize = maxDepth(root->left) + 1和int rightsize = maxDepth(root->right) + 1以及最后return (leftsize > rightsize) ? leftsize : rightsize返回值与leftsize和rightsize的关联。leftsize是每次记录以此函数中root为根结点的子二叉树的左孩子结点个数加上1(加1是还包括根结点，即左孩子加上根结点的总个数)，rightsize同理。最终返回的是此时子二叉树左孩子深度与右孩子深度的最大值。像此类的递归运用时，要思考运用递归的那一行与后面代码的中间逻辑关联。此关联多种多样，还需我们多多做题练习。
四，另一棵树的子树
题目：给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。其中，二叉树 tree 的一棵子树括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
分析：
显然，我们需要先遍历root这颗主树，当遇到结点数值与subRoot这颗树的根结点数值相同时就开始同时遍历这两颗树，判断这两颗树是否具有相同的逻辑和数值，如若在判断时这两个树在整个遍历过程中都有相同的逻辑和数值那么就返回true，否则就要继续往下面遍历root主树，当遍历完这颗root主树时返回false。
代码如下：
/** 二叉树的结构 * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ //设置此函数来进行判断root和subRoot两树结构和数值是否相等 bool isSameTree(struct TreeNode* root1, struct TreeNode* root2) { if (!root1 && !root2) { return true; } if ((root1 && !root2) || (!root1 && root2)) { return false; } if (root1->val != root2->val) { return false; } return isSameTree(root1->left, root2->left) && isSameTree(root1->right, root2->right); } bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) { //当两树同时或其中一颗为空时的情况 if (!root && !subRoot) { return true; } if (root && !subRoot) { return true; } //最终因为遍历时subRoot没有动，所以以次条件来判断返回false的情况 if (!root && subRoot) { return false; } //如果当根结点的数值相等时，root就不会继续往下面递归遍历了，这时会出问题 //例如:root中[1,1],subRoot中[1]，运行时输出false,但实际上是true //下面的注释判断是根据直接思维判断，即重心在返回true上 /*if (root->val == subRoot->val) { return isSameTree(root, subRoot); }*/ //运用反向判断，即如果不满足时继续可往下进行 if (root->val == subRoot->val) { if (isSameTree(root, subRoot)) { return true; } } //即只要找到与之匹配的情况时就结果就是true，用"||"控制这一点即可满足 return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot); }
具体的运用全部在解析中，重点放在条件的判断，要学会在以后的树中如何设定条件的判断。
学习建议：二叉树的运用是建立在二叉树基础算法之上，在学习到这一方面，必须要把二叉树的基本算法理解明白之后再上手。否则根基不稳后面会很吃亏。
