leetcode:二叉树oj题

目录

1.单值二叉树

2.相同的树

3.对称二叉树

4.二叉树的前序遍历

5.二叉树的中序遍历

6.二叉树的后序遍历

1.单值二叉树

https://leetcode.cn/problems/univalued-binary-tree/description/

        对于这道题,我们可以进行深度优先查找,当值相同时就继续向下查找,如左子树,如果值相同就继续向下搜索左子树节点的值,不同就返回false,不用查找

class Solution {
public:
    bool isUnivalTree(TreeNode* root) {
        if(root == NULL)
            return true;

        if(root->left != NULL)
        {
            if(root->val != root->left->val || !isUnivalTree(root->left))
                return false;
        }

        if(root->right != NULL)
        {
            if(root->val != root->right->val || !isUnivalTree(root->right))
                return false;
        }

        return true;
    }
};

2.相同的树

https://leetcode.cn/problems/same-tree/description/

        对于这道题,如果两个二叉树都为空，则两个二叉树相同.如果两个二叉树中有且只有一个为空，则两个二叉树一定不相同

        如果两个二叉树都不为空，那么首先判断它们的根节点的值是否相同，若不相同则两个二叉树一定不同，若相同，再分别判断两个二叉树的左子树是否相同以及右子树是否相同

class Solution {
public:
    bool isSameTree(TreeNode* p, 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);
        }
    }
};

3.对称二叉树

https://leetcode.cn/problems/symmetric-tree/

        对于这道题比较简单,从结构和值两方面考虑会简单得多.

结构:如果左右子树都为空,那么就对称,返回true,如果一方为空一方不为空,就返回false

值:左右子树的值不同,就返回false,相同就递归向下走,检查下一子树的值

bool isSameNode(struct TreeNode* left, struct TreeNode* right) {
    //结构相同
    if(left == NULL && right == NULL)
        return true;

    //结构不同
    if(left == NULL && right != NULL)
        return false;

    //结构不同
    if(left != NULL && right == NULL)
        return false;

    //值不同
    if(left->val != right->val)
        return false;
        
    return isSameNode(left->left, right->right) && isSameNode(left->right, right->left);
}

bool isSymmetric(struct TreeNode* root) {
    return isSameNode(root->left, root->right);
}

4.二叉树的前序遍历

https://leetcode.cn/problems/binary-tree-preorder-traversal/description/

        二叉树在前一节的过程中已经讲解,在此不多做解释,如不了解,可以观看https://blog.csdn.net/w200514/article/details/143101700?sharetype=blog&shareId=143101700&sharerefer=APP&sharesource=w200514&sharefrom=link

class Solution {
public:
    void preorder(TreeNode* root,vector<int> &res)
    {
        if(root==NULL)
            return;

        res.push_back(root->val);
        preorder(root->left,res);
        preorder(root->right,res);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        preorder(root,res);
        return  res;
    }
};

5.二叉树的中序遍历

https://leetcode.cn/problems/binary-tree-inorder-traversal/submissions/574731444/

class Solution {
public:
    void inorder(TreeNode* root,vector<int>& res)
    {
        if(root == NULL)
            return;
        inorder(root->left,res);
        res.push_back(root->val);
        inorder(root->right,res);
    }

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        inorder(root,res);
        return res;
    }
};

6.二叉树的后序遍历

https://leetcode.cn/problems/binary-tree-postorder-traversal/description/

class Solution {
public:
     void postorder(TreeNode* root,vector<int>& res)
    {
        if(root == NULL)
            return;
        postorder(root->left,res);
        postorder(root->right,res);
        res.push_back(root->val);
    }

    vector<int> postorderTraversal(TreeNode* root) {
        vector<int>res;
        postorder(root,res);
        return res;
    }
};