文章目录

• • • 单值二叉树
    • 相同的树
    • 另一棵树的子树
    • 对称二叉树
    • 翻转二叉树
    • 二叉树遍历
    • 二叉树的最大深度
    • 二叉树的前序遍历
    • 二叉树的中序遍历
    • 二叉树的后序遍历

单值二叉树

  如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。只有给定的树是单值二叉树时，才返回 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 
#include 
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;
}

  通过上面的题我们可以发现，二叉树很多操作都是基于递归实现的。所以要学好二叉树，必然要想掌握好递归。如果递归不熟悉就画递归图，多画几次就熟悉了。