二叉树基础题目

1. 二叉树的最大深度

这道题目显然就是遍整颗树, 计算遍历多少个节点

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;
        return max(maxDepth(root->left), maxDepth(root->right))+1;
    }
};

2.判断两个树是否相同:

同时遍历两个树的左边和右边, 如果出现不同的点，就返回false，如果出现相同的点那就跳过
如果同时遍历到底部，那么就返回true，如果其中一个已经到底部另外一个还没有到底部，那就直接返回false

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (!p && !q) {
            return true;
        }

        if (!p || !q) {
            return false;
        }

        if (p->val != q->val) {
            return false;
        }

        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

1. 对称二叉树

对称二叉树这道题目考查的是将一颗树上的左右两边给拆分。

bool dfs(struct TreeNode* l, struct TreeNode* r) {
    if (!r && !l) {
        return true;
    }

    if (!r || !l) {
        return false;
    }


    if (r->val != l->val) {
        return false;
    }

    return dfs(l->left, r->right) && dfs(l->right, r->left);
}


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

链表基础题目

1. 判断链表是否存在环, 主要的思路就是通过快慢指针来做的,
   首先我们设置一个快指针，然后设置一个慢指针,
2. 如果链表中存在环, 那么快慢指针一定会相遇, 那么这个时候退出返回true即可
3. 如果链表不存在环的话, 那么快慢指针一定不会相遇, 对应的条件也就是quick指针走到头了

bool hasCycle(struct ListNode *head) {
    if (!head || !head->next) return false;

    struct ListNode* slow = head;
    struct ListNode* quick = head->next;



    while (slow != quick) {
        if (!quick || !quick->next) return false;
        slow = slow->next;
        quick = quick->next->next;
    }

    return true;
}

1. 两个链表相加的问题
   分别就是分配两个指针