二叉树相关|单值二叉树|相同的树|对称二叉树|前序遍历|中序遍历|后序遍历|另一棵树的子树|二叉树遍历(C)

判断一棵树节点的值是不是都相等
用分治的思想解决
如果当前子树根等于左子树的根，等于右子树的根，可以认为这三个节点的值相等

如果当前三个节点没问题，就递归遍历左子树，如果还相等，可以得出5个节点都是相等的
如果递归到空树，就返回

bool isUnivalTree(struct 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);
}

是前序
判断的时候，先判断自己，再判断左右

拆解子问题
把树分成三个部分

1. 判断根和根
2. 判断左子树和左子树
3. 判断右子树和右子树
   但凡有一个不相等就返回false

bool isSameTree(struct TreeNode* p, struct 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);
}

拆解子问题
判断树的两个子树是否相等

1. 判断左子树的根和右子树的根
2. 判断左子树的左子树和右子树的右子树
3. 判断左子树的右子树和右子树的左子树
   如果有一个不相等就返回false

bool isSymmetricTree(struct TreeNode* p, struct TreeNode* q)
{
    if (p == NULL && q == NULL)
        return true;
  
    if (p == NULL || q == NULL)
        return false;
  
    if (p->val != q->val)
        return false;
  
    return isSymmetricTree(p->left, q->right)
        && isSymmetricTree(p->right, q->left);
}
  
bool isSymmetric(struct TreeNode* root)
{
    return isSymmetricTree(root->left, root->right);
}

前序遍历二叉树，把前序遍历的结果存到一个数组里面

遍历的时候需要定义一个数组的下标来存数据，因为每次递推，每个函数栈帧都会有一个i，形参不会影响实参，所以i会出现问题
所以定义一个局部变量，通过传地址来解决这个问题
不能用静态变量，否则每次调用函数都需要把下标置空

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 (root == NULL)
        return;
  
    a[(*pi)++] = root->val;
    preorder(root->left, a, pi);
    preorder(root->right, a, pi);
}
  
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int n = TreeSize(root);
    int* a = (int*)malloc(sizeof(int)*n);
  
    int i = 0;
    preorder(root, a, &i);
  
    *returnSize = n;
    return a;
}

这里需要返回数组的大小，通过返回二叉树的节点个数来实现

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 (root == NULL)
        return;
    
    inorder(root->left, a, pi);
    a[(*pi)++] = root->val;
    inorder(root->right, a, pi);
}

int* inorderTraversal(struct TreeNode* root, int* returnSize)
{
    int n = TreeSize(root);
    int* a = (int*)malloc(sizeof(int)*n);
    
    int i = 0;
    inorder(root, a, &i);
    
    *returnSize = n;
    return a;
}

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 (root == NULL)
        return;

    postorder(root->left, a, pi);
    postorder(root->right, a, pi);
    a[(*pi)++] = root->val;
}

int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    int n = TreeSize(root);
    int* a = (int*)malloc(sizeof(int)*n);

    int i = 0;
    postorder(root, a, &i);

    *returnSize = n;
    return a;
}

一棵树是不是另一棵的子树
先判断根节点，如果根节点相等再判断左子树和右子树

让左边树的每一棵子树都跟右边的子树比较一遍

bool isSameTree(struct TreeNode* p, struct 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);
}
  
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
    if (root == NULL)
        return false;
  
    if (root->val = subRoot->val)
    {
        if (isSameTree(root, subRoot))
            return true;
    }

    return isSubtree(root->left, subRoot)
        || isSubtree(root->right, subRoot);
}

最后返回bool值，左边比一下，右边比一下，如果左边找到了就不需要再比右边，直接返回上一层
如果都没有找到false || false还是false

先序遍历字符串，空树的位置用#替代
用前序遍历的方式构建二叉树
遇到空树返回，不再构建
再中序遍历，输出遍历结果