【数据结构】二叉树经典OJ题与OJ题解析

1. 单值二叉树

​​​​​​965. 单值二叉树 - 力扣（LeetCode）

bool isUnivalTree(struct TreeNode* root) {
    // 当前树
    if(root == NULL)
        return true;
    if(root->left && root->val != root->left->val)
        return false;

    if(root->right && root->val != root->right->val)
        return false;

    // 递归判断左右子树
    return isUnivalTree(root->left) && isUnivalTree(root->right);
}

2. 二叉树的最大深度

104. 二叉树的最大深度 - 力扣（LeetCode）

int max(int a,int b)
{
    if(a>b)
        return a;
    else
        return b;
}
// 当前深度为 max(左子树深度,右子树深度)+1
int maxDepth(struct TreeNode* root) {
    if(root == NULL)
        return 0;
    return max(maxDepth(root->left),maxDepth(root->right))+1;
}

3. 翻转二叉树

226. 翻转二叉树 - 力扣（LeetCode）

struct TreeNode* invertTree(struct TreeNode* root) {
    if(root == NULL)
        return NULL;
    // 左右交换
    struct TreeNode* tmp = root->left;
    root->left = root->right;
    root->right = tmp;
    invertTree(root->left);
    invertTree(root->right);
    return root;
}

4. 相同的树

100. 相同的树 - 力扣（LeetCode）

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    // 都为空返回true
    if(p == NULL && q == NULL)
        return true;
    // 一个为空一个不为空返回false
    if((p == NULL && q != NULL) || (p != NULL && q == NULL))
        return false;
    // 子树都返回true且当前节点值都相同才返回true
    return isSameTree(p->left,q->left) && isSameTree(p->right,q->right) && (p->val == q->val);
}

5.另一棵树的子树

572. 另一棵树的子树 - 力扣（LeetCode）

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    // 都为空返回true
    if(p == NULL && q == NULL)
        return true;
    // 一个为空一个不为空返回false
    if((p == NULL && q != NULL) || (p != NULL && q == NULL))
        return false;
    // 子树都返回true且当前节点值都相同才返回true
    return isSameTree(p->left,q->left) && isSameTree(p->right,q->right) && (p->val == q->val);
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
    if(root == NULL)
        return false;
    if(isSameTree(root,subRoot))
        return true;
    return isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
}

6.平衡二叉树

110. 平衡二叉树 - 力扣（LeetCode）

原思路：

int TreeDepth(struct TreeNode* root)
{
    if(root == NULL)
        return 0;
    return max(TreeDepth(root->left),TreeDepth(root->right))+1;
}

// 最好情况是O(N),最坏情况是O(N*N)
// 能不能优化到最坏情况O(N)？
bool isBalanced(struct TreeNode* root) {
    if(root == NULL)
        return true;
    if(abs(TreeDepth(root->left) - TreeDepth(root->right)) > 1)
        return false;
    else
        return isBalanced(root->left)&&isBalanced(root->right);
}

优化：

上面的代码是在用前序判断，有大量的计算高度重复，第一个根节点中已经递归计算了左子树的高度，然后到左孩子的时候又计算了一遍左子树的高度，重复了。

如果我们使用后序判断，第一个根节点的左和右的差我先不判断，我先判断我的左子树的左和右，到了左孩子，我继续不判断，继续左子树，一直到空。

bool _isBalanced(struct TreeNode* root, int* pDepth)
{
    if(root == NULL)
    {
        *pDepth = 0;
        return true;
    }
    else
    {
        int leftDepth = 0;
        int rightDepth = 0;
        // 先判断左树,判断不过直接返回
        if(_isBalanced(root->left,&leftDepth) == false)
            return false;
        // 再判断右树，判断不过直接返回
        if(_isBalanced(root->right,&rightDepth) == false)
            return false;
        // 最后判断自己
        if(abs(leftDepth - rightDepth) > 1)
            return false;
        *pDepth = max(leftDepth,rightDepth) + 1;
        return true;
    }
}

bool isBalanced(struct TreeNode* root) {
    int depth = 0;
    return _isBalanced(root,&depth);
}

7.二叉树遍历

​​​​​​二叉树遍历_牛客题霸_牛客网

typedef struct TreeNode
{
    char val;
    struct TreeNode* left;
    struct TreeNode* right;
}TreeNode_t;

// 中序遍历
void InOrder(TreeNode_t* root)
{
    if(root == NULL)
    {
        return;
    }
    else
    {
        InOrder(root->left);
        printf("%c ",root->val);
        InOrder(root->right);
    }
}

// 构建二叉树
TreeNode_t* creatTree(char* str,int* pi)
{
    if(str[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    else 
    {
        TreeNode_t* root = (TreeNode_t*)malloc(sizeof(TreeNode_t));
        root->val = str[*pi];
        (*pi)++;
        root->left = creatTree(str,pi);
        root->right = creatTree(str,pi);
        return root;
    }
    
}

int main() {

    char str[100];
    scanf("%s",str);
    int i = 0;
    TreeNode_t* root = creatTree(str,&i);
    InOrder(root);
    return 0;
}