leedcode 初级算法 树

链接

二叉树的最大深度

题目说明

求二叉树的最大深度

题目解析

使用递归求解即可

1
2
3
4
5
6
7
int maxDepth(struct TreeNode* root){
    if(root==NULL)
        return 0;
    int left=maxDepth(root->left);
    int right=maxDepth(root->right);
    return (left>=right?left+1:right+1);
}

验证二叉搜索树

题目描述

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

题目解析 方法一

递归验证即可。

或者中序遍历也可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool is_right(struct TreeNode* root,long low,long up)
{
    if(root==NULL)
        return true;
    if(root->val<=low||root->val>=up)
        return false;
    return is_right(root->left,low,root->val)&&is_right(root->right,root->val,up);
}

bool isValidBST(struct TreeNode* root){
    if(root==NULL)
        return true;
    return is_right(root,LONG_MIN,LONG_MAX);
}
题目解析 方法二

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int cur =INT_MIN;

bool isValidBST(struct TreeNode *root)
{
    printf("%d \n",cur);
    if (root)
    {
        if (!isValidBST(root->left))
            return false;
        printf("%d %d\n",cur,root->val);
        if (cur >= root->val)
            return false;
        cur = root->val;
        if (!isValidBST(root->right))
            return false;
    }
    return true;
}

对称二叉树

题目描述

给定一个二叉树，检查它是否是镜像对称的。

题目解析 方法一

中序遍历的方法不可行，形状判定很复杂。

使用递归，若像棵树镜像，则一棵树的左子树必定和另一棵树的右子树镜像。递归判断即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
bool is_right(struct TreeNode *left, struct TreeNode *right)
{
    if (!left && !right)
        return true;
    if (!left || !right)
        return false;
    return ((left->val == right->val) && is_right(left->left, right->right) && is_right(left->right, right->left));
}

bool isSymmetric(struct TreeNode *root)
{
    return is_right(root, root);
}
题目解析 方法二

使用队列啊ing递归改为迭代

每次从队列中取出要进行比较的两个结点，不相等的直接返回，相等则按相反顺序插入四个孩子到队列。直到队列为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution
{
public:
    bool isSymmetric(TreeNode *root)
    {
        deque<TreeNode *> q;
        q.push_back(root);
        q.push_back(root);
        while (!q.empty())
        {
            TreeNode *left = q.front();
            q.pop_front();
            TreeNode *right = q.front();
            q.pop_front();
            if (!left && !right)
                continue;
            if (!left || !right)
                return false;
            if (left->val != right->val)
                return false;
            //现在 left right 都不空 逆序存入
            q.push_back(left->left);
            q.push_back(right->right);
            q.push_back(left->right);
            q.push_back(right->left);
        }
        return true;
    }
};

二叉树的层序遍历

题目描述

层序遍历二叉树

题目解析 方法一

根结点入队。key_num记录每一层的个数，出队一个存入数组，入队其孩子。更新key_num。直到队空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution
{
public:
    vector<vector<int>> levelOrder(TreeNode *root)
    {
        vector<vector<int>> v;
        deque<TreeNode *> q;
        int key_num = 0;
        int temp_key_num = 0;
        if (!root)
            return v;
        q.push_back(root);
        key_num++;
        while (!q.empty())
        {
            vector<int> v1;
            TreeNode *t;
            while (key_num >= 1)
            {
                t = q.front();
                v1.push_back(t->val);
                q.pop_front();
                key_num--;
                if (t->left)
                {
                    q.push_back(t->left);
                    temp_key_num++;
                }
                if (t->right)
                {
                    q.push_back(t->right);
                    temp_key_num++;
                }
            }
            key_num = temp_key_num;
            temp_key_num = 0;
            v.push_back(v1);
        }
        return v;
    }
};

将有序数组转换为二叉搜索树

题目描述

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

题目解析 方法一

AVL树插入的时候可能涉及不平衡需要进行旋转，但是现在是从一个确定的数组中插入，故不需要进行旋转，只需要判断插入的顺序即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution
{
public:
    TreeNode *sortedArrayToBST(vector<int> &nums)
    {
        //TreeNode *root = (TreeNode *)malloc(sizeof(struct TreeNode));
        TreeNode *root = new TreeNode();
        root->val=nums.at(nums.size() / 2);
        root->left = insert(nums, 0, nums.size() / 2, root);
        root->right = insert(nums, nums.size() / 2 + 1, nums.size(), root);
        return root;
    }
    TreeNode *insert(vector<int> &nums, int low, int up, TreeNode *pa)
    {
        if (low != up)
        {
            //TreeNode *t = (TreeNode *)malloc(sizeof(struct TreeNode));
            TreeNode *t = new TreeNode();
            t->val=nums.at((low + up) / 2);
            t->left = insert(nums, low, (low + up) / 2, t);
            t->right = insert(nums, (low + up) / 2 + 1, up, t);
            return t;
        }
        return NULL;
    }
};