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);//不断后移比较
    }
}