• 【面试HOT100】链表&&树

    系列综述：
    💞目的：本系列是个人整理为了秋招面试的，整理期间苛求每个知识点，平衡理解简易度与深入程度。
    🥰来源：材料主要源于LeetCodeHot100进行的，每个知识点的修正和深入主要参考各平台大佬的文章，其中也可能含有少量的个人实验自证。
    🤭结语：如果有帮到你的地方，就点个赞和关注一下呗，谢谢🎈🎄🌷！！！
    🌈【C++】秋招&实习面经汇总篇

    文章目录

    😊点此到文末惊喜↩︎

    基本算法

    1. 双指针：适合线性表
    2. 哈希法：适合去重和查找
    3. while中记录并自增，然后进行结点处理（滑动窗口模板中类似）
    4. 链表基本模板
    #include 
using namespace std;

// 结点模板
template<typename T>
struct Node {
	T data;
	Node *next;
	Node() : next(nullptr) {}
	Node(const T &d) : data(d), next(nullptr) {}
};

// 删除 p 结点后面的元素
template<typename T>
void Remove(Node<T> *p) {
	// 确定两边安全性，然后删除中间
	if (p == nullptr || p->next == nullptr) 
		return;
	auto tmp = p->next->next;
	delete p->next;
	p->next = tmp;
}

//在 p 结点后面插入元素
template<typename T>
void Insert(Node<T> *p, const T &data) {
	auto tmp = new Node<T>(data);
	tmp->next = p->next;
	p->next = tmp;
}

//遍历链表
template<typename T, typename V>
void Traverse(Node<T> *p, const V &vistor) {
	while(p != nullptr) {
		vistor(p);	// 函数指针，灵活处理
		p = p->next;
	}
}

int main() {
	// 建立 链表结点
	auto p = new Node<int>(1);
	// 插入 链表结点
	Insert(p, 2);
	// 遍历 链表求和
	int sum = 0;
	Traverse(p, [&sum](const Node<int> *p) -> void { sum += p->data; });
	// 删除 链表
	Remove(p);
	return 0;
}

    • 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
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52

    链表篇

    160. 相交链表
    1. 问题
      • 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。
      • 如果两个链表不存在相交节点，返回 nullptr
    2. 思路
      • 相差同移法：先求出长度差值，然后长的移动差值次，再同时移动
      • 哈希法：先将一个存入哈希表，另一个开始遍历哈希表，第一个找到另一个即为第一个。
      • 交换遍历法：pa走到头后，从headB开始走。pb走到头后，从headA开始走。这样交替走路，两个到相同结点的长度是一样的
      在这里插入图片描述
    // 交换遍历
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode *pa = headA;
    ListNode *pb = headB;
    while (pa != pb) {
        (pa == nullptr) ? pa = headB : pa = pa->next;
        (pb == nullptr) ? pb = headA : pb = pb->next;
    }
    return pa;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    1. 总结
      • 注意if-else的条件分支是否分离判断
      • 查找和去重就思考哈希
    234. 回文链表
    1. 问题
      • 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。最大值 。
      • 链表题目通常不能使用数组进行处理
    2. 思路
      • 链表常用模板组合
    /**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) return true;
        // 找中点 1=>1 123=>2 1234=>2
        ListNode A_end = mid(head);
        ListNode B_start = A_end.next;
        A_end.next = null;
        // 翻转后半部分
        B_start = reverse(B_start);
        // 比对
        boolean res = compare(head, B_start);
        // 还原
        A_end.next = reverse(B_start);
        return res;
    }
    // 链表找中点，快慢指针法
    ListNode mid(ListNode head) {
        ListNode p = head;
        ListNode q = head;
        while(q.next != null && q.next.next != null) {
             p = p.next;
             q = q.next.next;
        }
        return p;
    }
    // 链表反转模板
    ListNode reverse(ListNode head) { // 三人行模板
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null) {
            ListNode temp = cur.next; // 松手先保存
            cur.next = pre;
            pre = cur; // 归位
            cur = temp;
        }
        return pre;
    }
    // 链表比对模板(len(B) <= len(A))
    boolean compare(ListNode A, ListNode B) {
        while(B != null) {
            if(A.val != B.val) return false;
            A = A.next;
            B = B.next;
        }
        return true;
    }
}

    • 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
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    141. 环形链表
    1. 问题
      • 给你一个链表的头节点 head ，判断链表中是否有环。
    2. 思路
      • 每次快指针移动两步，慢指针移动一步，同时移动直到快慢指针相遇即可。
    // 查找：使用hash存储，然后遍历环进行处理
bool hasCycle(ListNode *head) {
    ListNode* fast = head;
    ListNode* slow = head;
    while (true) {
        if (fast == nullptr || fast->next == nullptr) 
        	return false;
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow) break;
    }
    return true;
     
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    1. 判断环的长度：快慢指针相遇后继续移动，直到第二次相遇。两次相遇间的移动次数即为环的长度
    2. 判断环的入口：快慢指针相遇后，慢指针不动，另取一指针p指向链表头结点，然后节点p和节点slow同时移动，每次移动一步，二者相遇时指向的节点即为环的入口节点。
    142. 环形链表 II
    1. 问题
      • 给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
    2. 思路
      • 判断环的入口：快慢指针相遇后，慢指针不动，另取一指针p指向链表头结点，然后节点p和节点slow同时移动，每次移动一步，二者相遇时指向的节点即为环的入口节点。
    ListNode *detectCycle(ListNode *head) {
    ListNode* fast = head;
    ListNode* slow = head;
    while (true) {
        if (fast == nullptr || fast->next == nullptr) return nullptr;
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow) break;
    }
    fast = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
    return fast;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    21. 合并两个有序链表
    1. 问题
      • 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
    2. 思路
      • 虚拟头节点的使用
    // 每个链表有单独的指针处理
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode *vhead = new ListNode(-1, nullptr);
    ListNode *tail = vhead;	// 注意要赋值为vhead
    while (list1 != nullptr && list2 != nullptr) {
    	// 先保存目标结点，后进行处理
        ListNode *p;	
        if (list1->val < list2->val) {
            p = list1;
            list1 = list1->next;
        }else {
            p = list2;
            list2 = list2->next;
        }
        // 条件判断中共同的部分，分离出来
        tail->next = p;
        tail = tail->next;
    } 
    list1 == nullptr ? tail->next = list2 : tail->next = list1;
    return vhead->next;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    21. 合并N个有序链表
    1. 问题
      • 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
    2. 思路
      • 虚拟头节点的使用
    // 归并链表
ListNode* mergeLists(vector<ListNode*>& lists, int start, int end) {
	// 递归出口
    if (start == end) {
        return lists[start];
    }
    // 算法部分
    int mid = start + ((end - start) >> 1);
    ListNode* head1 = mergeLists(lists, start, mid);
    ListNode* head2 = mergeLists(lists, mid + 1, end);
    // 递归
    return merge(head1, head2);
}

// 合并排序链表
ListNode* merge(ListNode* head1, ListNode* head2) {
    ListNode* dummy = new ListNode();
    ListNode* cur = dummy;
    while (head1 != nullptr && head2 != nullptr) {
        if (head1->val < head2->val) {
            cur->next = head1;
            head1 = head1->next;
        }else {
            cur->next = head2;
            head2 = head2->next;
        }
        cur = cur->next;
    }
    // 收尾：注意链表末尾和虚拟头节点的回收
    cur->next = (head1 == nullptr) ? head2 : head1;
    ListNode* ret = dummy->next;
    dummy->next = nullptr;
    delete dummy;
    return ret;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
    if (lists.size() == 0) {
        return nullptr;
    }
    return mergeLists(lists, 0, lists.size() - 1);
}

    • 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
    19. 删除链表的倒数第 N 个结点
    1. 问题
      • 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
    2. 思路
      • 虚拟头节点的使用
      • 删除结点要使用保存其前一个结点的指针
    ListNode* removeNthFromEnd(ListNode* head, int n) {
    if(n < 0 || head == nullptr)
        return nullptr;
    // 快慢指针拉开n个节点的距离
    ListNode *vHead = new ListNode(0);
    vHead->next = head;
    ListNode *slow = vHead;
    ListNode *fast = vHead;
    // 让slow指向被删除节点的前一个
    while(n--){
        fast = fast->next;
    }
    // 同步移动
    while(fast->next != nullptr){
        fast = fast->next;
        slow = slow->next;
    }
    // 删除节点
    slow->next = slow->next->next;
    return vHead->next;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    2. 两数相加
    1. 问题
      • 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
      • 请你将两个数相加，并以相同形式返回一个表示和的链表。
        在这里插入图片描述
    2. 思路
      • 通过进位carry和补充虚拟结点，从而实现算法的统一处理
    class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        /* 定义一个新的链表用于存储求和的结果 */
        ListNode* dummyHead = new ListNode(0);
        ListNode* cur = dummyHead;
        /* 定义一个变量用于保存进位 */
        int carry = 0;

        /* 因为不知道l1和l2的长短所以只要有一个没有遍历完就继续遍历 遍历完的就不执行 */
        /* 
         * 第一次写while(l1 || l2)会错因为漏掉了最后一个进位《== 特别哟注意
        */
        while(l1 || l2 || carry){
            /* 只要不为空就继续求和 */
            if(l1 != NULL) carry += l1->val;
            if(l2 != NULL) carry += l2->val;
            /* 创建一个节点插入到新的链表并且值初始化为l1->val+l2->val的个位数 */
            ListNode* tmp = new ListNode(carry%10);
            /* 插入结点tmp因为是从头开始插入所以只需要每次更新cur */
            cur->next = tmp;
            cur = cur->next;
            /* 只要链表不为空就继续遍历下一个节点 */
            if(l1 != NULL) l1 = l1->next;
            if(l2 != NULL) l2 = l2->next;
            /* 获取上个节点的进位值 加到下个节点的运算中 */
            carry /= 10;
        }
        /* 注意这里不返回dummyHead因为这里相当于一个虚拟头节点 下一个才是正真的头节点 */
        return dummyHead->next;
    }
};

    • 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
    1. 总结
      • 补充虚拟的，从而将算法进行统一化处理
    24. 两两交换链表中的节点
    1. 问题
      • 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）
    2. 思路
      • 每次确定两个结点的前一个结点，并进行交互处理
    ListNode* swapPairs(ListNode* head){
	// 带安全检查的交换结点
   auto swap_list = [](ListNode *prev){
        if (prev != nullptr && prev->next != nullptr && prev->next->next != nullptr) {
            ListNode *front = prev->next;
            ListNode *back = front->next;
            front->next = back->next;
            back->next = front;
            prev->next = back;
        }
    };

    if(head == nullptr)
        return nullptr;
    // 单链表插/删，虚拟三件套
    ListNode* vHead = new ListNode(-1);
    vHead->next = head;					
    ListNode *cur = vHead;

    while(cur->next != nullptr && cur->next->next != nullptr){
        swap_list(cur);
        cur = cur->next->next;
    }
    return vHead->next;
}

    • 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
    1. 总结
      • 使用auto匿名函数封装链表基本操作
    25. K 个一组翻转链表
    1. 问题
      • 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
    2. 算法
      • 栈：可以用来处理逆序问题
    ListNode* reverseKGroup(ListNode* head, int k) {
    stack<ListNode*> stk;
    ListNode* res=new ListNode;
    ListNode* p=res,*q;
    int i;
    while(head){
        for(i=0;head&&i<k;i++){//k个一组进栈
            stk.push(head);
            head=head->next;
        }
        if(i!=k)break;//不成一组跳出
        while(!stk.empty()){//逆序出栈
            p->next=stk.top();
            p=stk.top();
            stk.pop();
        }
        q=head;
    }
    p->next=q;//接上余下的点
    return res->next;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    148. 排序链表
    1. 问题
      • 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表
    2. 思路
      • 归并
    ListNode* sortList(ListNode* head) {
    ListNode dummyHead(0);
    dummyHead.next = head;
    auto p = head;
    int length = 0;
    while (p) {
        ++length;
        p = p->next;
    }
    
    for (int size = 1; size < length; size <<= 1) {
        auto cur = dummyHead.next;
        auto tail = &dummyHead;
        
        while (cur) {
            auto left = cur;
            auto right = cut(left, size); // left->@->@ right->@->@->@...
            cur = cut(right, size); // left->@->@ right->@->@  cur->@->...
            
            tail->next = merge(left, right);
            while (tail->next) {
                tail = tail->next;
            }
        }
    }
    return dummyHead.next;
}
// 分离链表
ListNode* cut(ListNode* head, int n) {
	// p指向链表的第n个
    auto p = head;
    while (--n && p) {
        p = p->next;
    }
    if (p == nullptr) return nullptr;
    // 返回链表后的结点，并将该段链表分离
    auto next = p->next;
    p->next = nullptr;
    return next;
}
// 合并两个有序链表
ListNode* merge(ListNode* l1, ListNode* l2) {
    ListNode dummyHead(0);
    auto p = &dummyHead;
    while (l1 && l2) {
        if (l1->val < l2->val) {
            p->next = l1;
            p = l1;
            l1 = l1->next;       
        } else {
            p->next = l2;
            p = l2;
            l2 = l2->next;
        }
    }
    p->next = (l1 ? l1 : l2);
    return dummyHead.next;
}

    • 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
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    146. LRU 缓存
    class LRUCache {
public:
    LRUCache(int capacity) : cap(capacity) {
    }

    int get(int key) {
        if (map.find(key) == map.end()) return -1;
        auto key_value = *map[key];
        cache.erase(map[key]);
        cache.push_front(key_value);
        map[key] = cache.begin();
        return key_value.second;
    }

    void put(int key, int value) {
    	// 先清除
        if (map.find(key) == map.end()) {
            if (cache.size() == cap) {
                map.erase(cache.back().first);
                cache.pop_back();
            }
        }
        else {
            cache.erase(map[key]);
        }
        cache.push_front({key, value});
        map[key] = cache.begin();
    }
private:
    int cap;
    list<pair<int, int>> cache;
    unordered_map<int, list<pair<int, int>>::iterator> map;
};

    • 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

    树篇

    基本概述
    1. 二叉树数据结构
      struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
    二叉树深度优先遍历
    1. 递归式
      // 前序遍历
void Traversal(TreeNode *root) {
  if (root == nullptr) return ;
  Doing(root->val);       // 中
  Traversal(root->left);  // 左
  Traversal(root->right); // 右
}
// 中序遍历
void Traversal(TreeNode *root) {
  if (root == nullptr) return ;
  Traversal(root->left);  // 左
  Doing(root->val);       // 中
  Traversal(root->right); // 右
}
// 后序遍历
void Traversal(TreeNode *root, vector<int> vec) {
 if (root == nullptr) return ;
  Traversal(root->left);  // 左
  Traversal(root->right); // 右
  vec.emplace_back(root->val);// 中
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
      • 14
      • 15
      • 16
      • 17
      • 18
      • 19
      • 20
      • 21
    2. 非递归：将前序、中序和后序统一化处理，将遍历核心顺序进行逆序转化
      • 算法遍历部分的逆序
      • 对于值节点的处理
      vector<int> Traversal(TreeNode* root) {
    // 初始化
    vector<int> result;		// 结果容器
    stack<TreeNode*> st;	// 深度的栈
    if (root != NULL) 		// 根非空则入栈
    	st.push(root);
    // 遍历源容器
    while (!st.empty()) {
        TreeNode* node = st.top();	//   
        if (node != NULL) {
            st.pop();
        // 算法变化的部分，遍历的逆序
            // 中
            st.push(node);                          
            st.push(NULL);
			// 右
            if (node->right) st.push(node->right); 
            // 左
            if (node->left) st.push(node->left);    
        } else {
        	// 对值节点的处理
            st.pop();// 弹出空值结点
            node = st.top();
            st.pop();
            // 结点处理
            result.push_back(node->val);
        }
    }
    return result;
}

      • 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
    二叉树广度优先遍历
    1. 递归法
      // 递归参数，如果需要修改要进行引用传递
void traversal(TreeNode* cur, vector<vector<int>>& result, int depth) {
	// 递归出口
    if (cur == nullptr) return;
    // 递归体
    if (result.size() == depth) // 扩容
    	result.push_back(vector<int>());// 原地构建数组
    result[depth].push_back(cur->val);// 顺序压入对应深度的数组中
    order(cur->left, result, depth + 1);
    order(cur->right, result, depth + 1);
}
vector<vector<int>> levelOrder(TreeNode* root) {
	// 初始化：一般为递归形参
    vector<vector<int>> result;
    int depth = 0;
    // 递归调用
    traversal(root, result, depth);
    // 返回结果
    return result;
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
      • 14
      • 15
      • 16
      • 17
      • 18
      • 19
      • 20
    2. 非递归法
    vector<vector<int>> levelOrder(TreeNode* root) {
    // 初始化
    vector<vector<int>> result;	// 结果容器
    queue<TreeNode*> que;		// 广度的队列
    if(root != nullptr)			// 根非空则入列 
    	que.push(root);
   // 算法
    while (!que.empty()) {		// 队列非空
        vector<int> vec;		// 结果存放
        TreeNode* node; 		// 过程记录
        int size = que.size();	// 初始化：记录每层要遍历的根节点数量
        for (int i = 0; i < size; i++) {	// que.size()会变化
            // 处理结点
            node = que.front();	// 记录队首结点
            que.pop();			// 弹出队首结点
            if (node->left) que.push(node->left);
            if (node->right) que.push(node->right);
            // doing：处理结点
			vec.push_back(node->val);
        }
        // 将每层筛选元素压入结果数组中
        result.push_back(vec);
    }
    // 输出
    return result;
}

    • 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
    226. 翻转二叉树
    1. 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
    2. 思路
      • 前序遍历
    void traversal(TreeNode *cur){
    // 结束条件
    if(cur == nullptr)
        return ;
    swap(cur->left, cur->right);
    if(cur->left)  traversal(cur->left);
    if(cur->right)  traversal(cur->right);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    101. 对称二叉树
    1. 给你一个二叉树的根节点 root ， 检查它是否轴对称。
    2. 思路
      • 单层条件尝试
    bool ismirror(TreeNode* t1,TreeNode* t2){
    if(t1==NULL&&t2==NULL)//都为空
        return true;
    if(t1==NULL||t2==NULL)//有一个为空
        return false;
    return (t1->val==t2->val)&&ismirror(t1->left,t2->right)
    	&&ismirror(t1->right,t2->left);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    543. 二叉树的直径
    1. 问题
      • 给你一棵二叉树的根节点，返回该树的 直径 。
      • 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
    2. 思路
      • 最长一定是以某个结点为根节点的子树的左右子树高度之和
    int diameterOfBinaryTree(TreeNode* root)
{
    int distance = 0;
    dfs(root, distance);
    return distance;
}

// distance等价于全局变量
int dfs(TreeNode *root, int &distance){
    if (root == nullptr)
        return 0;
    int left = dfs(root->left, distance);	// 左边深度
    int right = dfs(root->right, distance);	// 右边深度
    distance = max(left + right, distance);	// 
    // 获取当前树的左子树和右子树深度的较大值，加 1 （本层深度）
    return max(left, right) + 1;	// 最大深度
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    108. 将有序数组转换为二叉搜索树
    1. 问题
      • 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
      • 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
    2. 思路
      • 建根和划分
    TreeNode* Translate(vector<int>& nums, int left, int right) {
   if (left > right) return nullptr;
   // 建根
   int mid = left + ((right - left) / 2);
   TreeNode *root = new TreeNode(nums[mid]);
   // 划分
   root->left = Translate(nums, left, mid-1);
   root->right = Translate(nums, mid+1, right);
   // 返回
   return root;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    108. 将有序数组转换为二叉搜索树
    1. 问题
      • 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
      • 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
    2. 思路
      • 建根和划分
    TreeNode* Translate(vector<int>& nums, int left, int right) {
   if (left > right) return nullptr;
   // 建根
   int mid = left + ((right - left) / 2);
   TreeNode *root = new TreeNode(nums[mid]);
   // 划分
   root->left = Translate(nums, left, mid-1);
   root->right = Translate(nums, mid+1, right);
   // 返回
   return root;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    98. 验证二叉搜索树
    1. 问题
      • 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。对值不超过 1 的二叉树。
    2. 思路
      • 二叉树的中序遍历是递增顺序的
      • 判断左小右大
    // 中序递增
long pre = MIN_                                                                                                                                                                                                                       ;
public boolean isValidBST(TreeNode root) {
   if (root == null) {
       return true;
   }
   // 访问左子树
   if (!isValidBST(root.left)) {
       return false;
   }
   // 访问当前节点：如果当前节点小于等于中序遍历的前一个节点，说明不满足BST，返回 false；否则继续遍历。
   if (root.val <= pre) {	// 严格递增
       return false;
   }
   pre = root.val;
   // 访问右子树
   return isValidBST(root.right);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    树相关题目

    少年，我观你骨骼清奇，颖悟绝伦，必成人中龙凤。
    不如点赞·收藏·关注一波

    🚩点此跳转到首行↩︎

    参考博客

    1. 前缀和问题
    2. 单调队列
    3. 快速链表quicklist
    4. 《深入理解计算机系统》
    5. 侯捷C++全系列视频
    6. 待定引用
    7. 待定引用
    8. 待定引用
  • 相关阅读:
    C++STL详解（六）unordered_set&unordered_map介绍
    学习软件测试需要注意的几点
    Rebex Total Pack R6.9 Crack
    Linux线程编程
    ETL可视化工具 DataX -- 安装部署 ( 二)
    2.每天进步一点点-Python爬虫需要了解一下基础的web相关内容
    Api -- 连接世界的Super Star
    Django数据库增删改查
    MQ - 24 Pulsar集群架构设计与实现
    Linux 内核中根据文件inode号获取其对应的struct inode
  • 原文地址：https://blog.csdn.net/qq_43840665/article/details/133845780