1.二叉树链式结构的实现
1.1 前置说明
在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。本文准备讲述一些二叉树的基础知识，此处手动快速创建一棵简单的二叉树，来快速进入二叉树 操作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。
typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType _data; struct BinaryTreeNode* _left; struct BinaryTreeNode* _right; }BTNode; BTNode* CreatBinaryTree() { BTNode* node1 = BuyNode(1); BTNode* node2 = BuyNode(2); BTNode* node3 = BuyNode(3); BTNode* node4 = BuyNode(4); BTNode* node5 = BuyNode(5); BTNode* node6 = BuyNode(6); node1->_left = node2; node1->_right = node4; node2->_left = node3; node4->_left = node5; node4->_right = node6; return node1; }
注意：上述代码并不是创建二叉树的方式，真正创建二叉树方式后序详解重点讲解。 再看二叉树基本操作前，再回顾下二叉树的概念，详情可见树和堆的一些基础知识
二叉树是:
1. 空树
2. 非空：根节点，根节点的左子树、根节点的右子树组成的。
从概念中可以看出，二叉树定义是递归式的//为空返回判断，因此后序基本操作中基本都是按照该概念实现的。
1.2二叉树的遍历
1.2.1 前序、中序以及后序遍历
学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉 树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历 是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。
按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：
- 1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
- 2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
- 3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后
由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为 根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
下面主要分析前序递归遍历，中序与后序图解类似，大家可自己动手绘制。
前序遍历递归图解：
一直往下，遇空返回，再读下一行代码
- 前序遍历结果：1 2 3 4 5 6
- 中序遍历结果：3 2 1 5 4 6
- 后序遍历结果：3 2 5 6 4 1
2.二叉树例题
965.单值二叉树
如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时，才返回 true；否则返回 false。
示例 1：
输入：[1,1,1,1,1,null,1]
输出：true
示例 2：
输入：[2,2,2,5,2]
输出：false
对反例判断完后，就开始递归
class Solution { public: bool isUnivalTree(TreeNode* root) { // 先进行三个反例的判断，就开始递归啦 if (root == NULL) 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); } };
理解：层层传递，先一条路走到底，NULL之后开始开始往回报，碰到右子树就传过来执行代码了，最后返回到院长为空
二叉树查找值为x的结点
返回值的设置NULL，都不是就返回为空，再往下读，引入lret/rret返回地址，
如果上面是反例法，不是就往下移
那么这个就是移动成立条件return，不成立NULL
100.相同的树
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1：
输入：p = [1,2,3], q = [1,2,3]
输出：true
示例 2：
输入：p = [1,2], q = [1,null,2]
输出：false
思路：先左再右，没有不一样就是一样，返回ture
class Solution { public: bool isSameTree(TreeNode* p, 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); //先左再右，没有不一样就是一样，返回ture } };
144.二叉树的前序遍历
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
int TreeSize(struct TreeNode* root) { return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1; } void preorder(struct TreeNode* root, int* res, int* resSize) { if (root == NULL) { return; } res[(*resSize)++] = root->val; // 读取根数据 preorder(root->left, res, resSize); // 读取左子树 preorder(root->right, res, resSize); // 读取右子树 } int* preorderTraversal(struct TreeNode* root, int* returnSize) { *returnSize = TreeSize(root); int* res = (int*)malloc((*returnSize) * sizeof(int)); // 分配内存 *returnSize = 0; preorder(root, res, returnSize); // 进行先序遍历 return res; }
572. 另一棵树的子树
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
示例 1：
输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true
bool isSametree(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; } else { return isSametree(p->left, q->left) && isSametree(p->right, q->right); } } } bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) { if (subRoot == NULL) { return true; } else if (root == NULL && subRoot != NULL) { return false; } if (true == isSametree(root, subRoot))//关键步骤调用空空真函数比较 { return true; } else { return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);//不断后移比较 } }
