单值二叉树
如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。只有给定的树是单值二叉树时，才返回 true；否则返回 false。
这道题的思路比较简单，就是记录根节点的值，然后进行遍历，如果遇到不同的值就返回false，如果遍历完之后，仍旧没有不同的值，就返回true。
bool isUnivalTree(struct TreeNode* root){ if(NULL == root) 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); }
相同的树
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
这道题和上一道题的思路类似，两个树同步进行遍历，如果遇到不同的就返回false，遍历完之后仍旧没有相同值就返回true。
bool isSameTree(struct TreeNode* p, struct TreeNode* q){ if(NULL == p && NULL == q) return true; if(NULL == p || NULL == q) return false; if(p->val != q->val) return false; return isSameTree(p->left, q->left) && isSameTree(p->right, q->right); }
另一棵树的子树
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
这道题需要基于上一道题来做，如果没有上一道题的铺垫，这道题的难度会再上一个系数。解题思路就是将每一个子树与subRoot进行比较，有相同的就返回true，否则就返回false
bool isSameTree(struct TreeNode* p, struct TreeNode* q){ if(NULL == p && NULL == q) return true; if(NULL == p || NULL == q) return false; if(p->val != q->val) return false; return isSameTree(p->left, q->left) && isSameTree(p->right, q->right); } bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){ if(NULL == root) return false; if(isSameTree(root, subRoot)) return true; return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot); }
对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
本质还是判断两个树是否相同，不过是左子树与左子树比、右子树与右子树比，换成了左子树与右子树比、右子树与左子树比。
bool isSameTree(struct TreeNode* p, struct TreeNode* q){ if(NULL == p && NULL == q) return true; if(NULL == p || NULL == q) return false; if(p->val != q->val) return false; return isSameTree(p->left, q->right) && isSameTree(p->right, q->left); } bool isSymmetric(struct TreeNode* root){ return isSameTree(root->left, root->right); }
翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
这道题的核心在于交换左右子树，实际上应该保留原二叉树的，但是我懒，就直接交换了。
struct TreeNode* invertTree(struct TreeNode* root){ if(NULL == root) return NULL; invertTree(root->left); invertTree(root->right); struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode)); node = root->left; root->left = root->right; root->right = node; return root; }
二叉树遍历
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
这道题就是简单的前序构建二叉树，然后中序遍历。
#include <stdio.h> #include <stdlib.h> struct TreeNode { char val; struct TreeNode* left; struct TreeNode* right; }; struct TreeNode* rebulidTree(char* str, int* pi) { if('#' == str[*pi]) { (*pi)++; return NULL; } struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode)); root->val = str[(*pi)++]; root->left = rebulidTree(str, pi); root->right = rebulidTree(str, pi); return root; } void InOrder(struct TreeNode* root) { if(NULL == root) return; InOrder(root->left); printf("%c ", root->val); InOrder(root->right); } int main() { char str[100]; scanf("%s", str); int i = 0; struct TreeNode* root = rebulidTree(str, &i); InOrder(root); return 0; }
二叉树的最大深度
给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
实际上就是求二叉树的高度。
int maxDepth(struct TreeNode* root){ if(NULL == root) return 0; int left = maxDepth(root->left); int right = maxDepth(root->right); return (left > right ? left : right) + 1; }
二叉树的前序遍历
给你二叉树的根节点 root ，返回它节点值的前序遍历。
int TreeSize(struct TreeNode* root) { return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1; } void preorder(struct TreeNode* root, int* a, int* pi) { if(NULL == root) return; a[(*pi)++] = root->val; preorder(root->left, a, pi); preorder(root->right, a, pi); } int* preorderTraversal(struct TreeNode* root, int* returnSize){ *returnSize = TreeSize(root); int* a = (int*)malloc(*returnSize * sizeof(int)); int i = 0; preorder(root, a, &i); return a; }
二叉树的中序遍历
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
int TreeSize(struct TreeNode* root) { return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1; } void InOrder(struct TreeNode* root, int* a, int* pi) { if(NULL == root) return; InOrder(root->left, a, pi); a[(*pi)++] = root->val; InOrder(root->right, a, pi); } int* inorderTraversal(struct TreeNode* root, int* returnSize){ *returnSize = TreeSize(root); int* a = (int*)malloc(*returnSize * sizeof(int)); int i = 0; InOrder(root, a, &i); return a; }
二叉树的后序遍历
给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
int TreeSize(struct TreeNode* root) { return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1; } void postOrder(struct TreeNode* root, int* a, int* pi) { if(NULL == root) return; postOrder(root->left, a, pi); postOrder(root->right, a, pi); a[(*pi)++] = root->val; } int* postorderTraversal(struct TreeNode* root, int* returnSize){ *returnSize = TreeSize(root); int* a = (int*)malloc(*returnSize * sizeof(int)); int i = 0; postOrder(root, a, &i); return a; }
通过上面的题我们可以发现，二叉树很多操作都是基于递归实现的。所以要学好二叉树，必然要想掌握好递归。如果递归不熟悉就画递归图，多画几次就熟悉了。
