发表于 2024-06-04 更新于 2026-01-11

树

	94. 二叉树的中序遍历	HOT100	递归+迭代	morris morris 不改结构（类似线索二叉树），官解
	144. 二叉树的前序遍历		递归+迭代	morris:和中序只要改if (pre->right == nullptr) { res.push_back(root->val);
	145. 二叉树的后序遍历		递归+迭代	morris 把94中序的左右颠倒
层序	102. 二叉树的层序遍历	HOT100	递归+迭代
	429. N 叉树的层序遍历		没啥区别
	103. 二叉树的锯齿形层序遍历 LCR 151. 彩灯装饰记录 III		102倒过来
	107. 二叉树的层序遍历 II		和102没区别，倒过来就行
	662. 二叉树最大宽度		bfs,注意越界ull	dfs
	958. 二叉树的完全性检验		层次遍历，空值也入队，当出队值为空时判断队列剩下元素是否都为空，为则完全二叉树	dfs 也可，和662类似
递归	199. 二叉树的右视图	HOT100	递归+迭代
	104. 二叉树的最大深度	HOT100	递归+迭代
	559. N 叉树的最大深度		递归+迭代
	111. 二叉树的最小深度		递归（前序后续）+迭代
	226. 翻转二叉树 LCR 144. 翻转二叉树	HOT100	递归+迭代
	110. 平衡二叉树		后序（递归+迭代）+前序前序，时间复杂度
	222. 完全二叉树的节点个数		完全二叉树性质	二分+位运算（官解）
	1325. 删除给定值的叶子节点		后序
	3693 · 克隆 N 叉树 1490. 克隆 N 叉树		dfs or bfs
	617. 合并二叉树		dfs or bfs
一篇文章带你吃透对称性递归(思路分析+解题模板+案例解读)	100. 相同的树		dfs+迭代
	101. 对称二叉树	HOT100	递归+迭代	100升级
	572. 另一棵树的子树		100+每个比对前序+kmp，哈希树（官解思路）	100升级
	LCR 143. 子结构判断		dfs+迭代	和572类似，但注意不同
路径非自顶向下：	543. 二叉树的直径	HOT100	bfs+dfs
	124. 二叉树中的最大路径和	HOT100	543升级版	带路径
	1245(3686 · N 叉树的直径 - LintCode)
	2246. 相邻字符不同的最长路径		124升级（微软面试)函数要带引用不然超时
	687. 最长同值路径
自顶向下：	257. 二叉树的所有路径
	112. 路径总和		bfs+dfs
	113. 路径总和 II LCR 153. 二叉树中和为目标值的路径		112 输出路径版
	129. 求根节点到叶节点数字之和		bfs+dfs 113改改
	437. 路径总和 III	HOT100	双dfs（可打印出所有路径） or 前缀和
	988. 从叶结点开始的最小字符串
公共祖先	236. 二叉树的最近公共祖先	HOT100	dfs or 哈希存父节点(官解)
	235. 二叉搜索树的最近公共祖先
构造	105. 从前序与中序遍历序列构造二叉树	HOT100	输出后序，迭代
	106. 从中序与后序遍历序列构造二叉树		105迭代改为左右更改，从后往前
二叉搜索树	98. 验证二叉搜索树	HOT100	中序，中序迭代
	230. 二叉搜索树中第K小的元素	HOT100	中序，中序迭代多次查询，记录k（官解bst）
	LCR 174. 寻找二叉搜索树中的目标节点		230倒过来
	108. 将有序数组转换为二叉搜索树	HOT100	先序
	450. 删除二叉搜索树中的节点		递归or迭代
	701. 二叉搜索树中的插入操作		递归or迭代
	LCR 155. 将二叉搜索树转化为排序的双向链表 426（要vip）		中序（递归or迭代
	538. 把二叉搜索树转换为累加树 1038. 从二叉搜索树到更大和树		反中序（可morris
链表	114. 二叉树展开为链表		后序、后序迭代
序列化	297. 二叉树的序列化与反序列化		前序+bfs
	652. 寻找重复的子树		序列化+dfs
建图（？）	863. 二叉树中所有距离为 K 的结点		用哈希存父节点变成图遍历（bfsor dfs）官解

3686 · N 叉树的直径

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */

class Solution {
public:
    /**
     * @param root: the root of the tree
     * @return: Maximum diameter of the N-ary Tree
     */
    int dfs(UndirectedGraphNode * root,int& ans)
    {
        if(!root)return 0;
        int l=0,r=0;
        for(auto nei:root->neighbors)
        {
            int cur=dfs(nei,ans);
            if(cur>l)
            {
                r=l,l=cur;
            }
            else if(cur>r)r=cur;
        }
        ans=max(l+r+1,ans);
        return max(l,r)+1;
    }
    int diameter(UndirectedGraphNode *root) {
        // write your code here
        if(!root)return 0;
        int ans=0;
        dfs(root,ans);
        return ans-1;
    }
};

二叉树的最近公共祖先(含输入)

#include<bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<endl
#define ll long long
using namespace std;
typedef unsigned long long ull;
const int N=1e3+10;
int n,p,q;
struct TreeNode 
{
    int val;
    int left;
    int right;
    TreeNode() : val(0), left(-1), right(-1) {}
    TreeNode(int x) : val(x), left(-1), right(-1) {}
//    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
TreeNode nodes[N];

int lowestCommonAncestor(int root, int p, int q) {
        if(root==-1||root==p||root==q)return root;
        int lchild=lowestCommonAncestor(nodes[root].left,p,q);
        int rchild=lowestCommonAncestor(nodes[root].right,p,q);
        if(lchild!=-1&&rchild!=-1)
        {
            return root;
        }
        else if(lchild!=-1)
        {
            return lchild;
        }
        else if(rchild!=-1)
        {
            return rchild;
        }
        return -1;
    }
int main() 
{
    int n;
    scanf("%d%d%d", &n, &p, &q);
    for (int i = 0; i < n; i++) 
    {
        scanf("%d%d", &nodes[i].left, &nodes[i].right);
    }
    printf("%d", lowestCommonAncestor(0, p, q));
    return 0;
}

先序中序还原二叉树(后序输出)

#include<bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<endl
#define ll long long
using namespace std;
typedef unsigned long long ull;
const int N=1e3+10;
int n;
struct TreeNode 
{
    int val;
    TreeNode * left;
    TreeNode * right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    // TreeNode() : val(0), left(-1), right(-1) {}
    // TreeNode(int x) : val(x), left(-1), right(-1) {}
   TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
TreeNode nodes[N];

vector<int> pre, in, post;

    TreeNode * buildTree(int preL, int preR, int inL, int inR) 
    {
        if (preL > preR) 
        {
            return nullptr;
        }
        TreeNode* root=new TreeNode(pre[preL]);
        int inIndexOfRoot;
        for (int i = inL; i <= inR; i++) 
        {
            if (in[i] == root->val) 
            {
                inIndexOfRoot = i;
                break;
            }
        }
        int leftCount = inIndexOfRoot - inL;
        root->left = buildTree(preL + 1, preL + leftCount, inL, inIndexOfRoot - 1);
        root->right = buildTree(preL + leftCount + 1, preR, inIndexOfRoot + 1, inR);
        return root;
    }
void postOrder(TreeNode * root) 
{
    if (root == nullptr) 
    {
        return;
    }
    postOrder(root->left);
    postOrder(root->right);
    post.push_back(root->val);
}
int main() {
    int n, x;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) 
    {
        scanf("%d", &x);
        pre.push_back(x);
    }
    for (int i = 0; i < n; i++) 
    {
        scanf("%d", &x);
        in.push_back(x);
    }
    TreeNode * root = buildTree(0, n - 1, 0, n - 1);
    postOrder(root);
    for (int i = 0; i < (int)post.size(); i++) 
    {
        printf("%d", post[i]);
        if (i < (int)post.size() - 1) 
        {
            printf(" ");
        }
    }
    return 0;
}

3693 · 克隆 N 叉树

dfs

/**
 * Definition of NBranchTree:
 * class NBranchTree {
 * public:
 *     int val;
 *     vector<NBranchTree> children;
 *     NBranchTree(int _val) {
 *         this->val = val;
 *     }
 *     NBranchTree(int _val, vector<NBranchTree*> _children) {
 *         val = _val;
 *         children = _children;
 *     }
 * };
 */

class Solution {
public:
    /**
     * @param root: The root node of a n-branch tree.
     * @return: The cloned tree.
     */
    NBranchTree* cloneTree(NBranchTree *root) {
        // --- write your code here ---
        if(!root)return nullptr;
        vector<NBranchTree*> chr;
        for(auto x:root->children)
        {
            NBranchTree* child=cloneTree(x);
            chr.push_back(child);
        }
        return new NBranchTree(root->val,chr);
    }
};

bfs

/**
 * Definition of NBranchTree:
 * class NBranchTree {
 * public:
 *     int val;
 *     vector<NBranchTree> children;
 *     NBranchTree(int _val) {
 *         this->val = val;
 *     }
 *     NBranchTree(int _val, vector<NBranchTree*> _children) {
 *         val = _val;
 *         children = _children;
 *     }
 * };
 */
#define debug(a) cout<<#a<<"="<<a<<" "
class Solution {
public:
    /**
     * @param root: The root node of a n-branch tree.
     * @return: The cloned tree.
     */
     unordered_map<NBranchTree *,NBranchTree *>umap;
    NBranchTree* cloneTree(NBranchTree *root) {
        // --- write your code here ---
        if(!root)return nullptr;
        vector<NBranchTree*> chr;
        queue<NBranchTree*>q;

        q.push(root);
        NBranchTree* head=nullptr;
        while(!q.empty())
        {
            int size=q.size();
           
            for(int i=0;i<size;i++)
            {
                NBranchTree* node=q.front();
                q.pop();
                NBranchTree* clonenode=new NBranchTree(node->val);
               
                // debug(clonenode->val);
                if(umap.count(node))
                { 
                    NBranchTree* parent = umap[node];
                    (parent->children).push_back(clonenode);
                }
                else
                {
                    head=clonenode;
                }
                for(auto x:node->children)
                {
                    umap[x]=clonenode;
                    q.push(x);
                }
                
            }
        }
        return head;
    }
};

谷歌面试（线段树/区间树）

Problem:

Given a list of timestamp ranges, each range represents a user using a Google service. Write a function that returns all users using the Google services at specific query timestamp.

A range can be represented as: [starting, ending], e.g., [1, 3] or [0, 10] and so on.

For instance, given a list of ranges:

[0, 5]
[6, 8]
[2, 9]
[4, 10]
[3, 5]

Searching through the above with a query timestamp of 3 should return:

[0, 2, 4]

because [0, 5], [2, 9], [3, 5] contain timestamp 3.

You’ll need to do a large number of queries through a largely static set of ranges that are provided at the start of the program.
It’s fine to prepare the data in some way such that the search operation is fast.

#include <iostream>
#include <vector>
#include <algorithm>
#include <memory>

using namespace std;

// 定义区间结构，增加 id 以便追踪原始用户
struct Interval {
    int start;
    int end;
    int id; // 用户下标
};

// 区间树节点
struct Node {
    int center;
    Node* left = nullptr;
    Node* right = nullptr;
    
    // 存储经过该节点中心点的区间
    vector<Interval> by_start; // 按 start 升序
    vector<Interval> by_end;   // 按 end 降序

    ~Node() {
        delete left;
        delete right;
    }
};

class IntervalTree {
private:
    Node* root;

    // 递归构建树
    Node* build(const vector<Interval>& intervals) {
        if (intervals.empty()) return nullptr;

        // 1. 确定中心点 (使用中点，也可优化为中位数)
        int min_t = intervals[0].start;
        int max_t = intervals[0].end;
        for (const auto& i : intervals) {
            min_t = min(min_t, i.start);
            max_t = max(max_t, i.end);
        }
        int center = min_t + (max_t - min_t) / 2;

        vector<Interval> lefts;
        vector<Interval> rights;
        vector<Interval> overlaps;

        // 2. 将区间分发到左、右或中间
        for (const auto& i : intervals) {
            if (i.end < center) {
                lefts.push_back(i);
            } else if (i.start > center) {
                rights.push_back(i);
            } else {
                overlaps.push_back(i);
            }
        }

        Node* node = new Node();
        node->center = center;

        // 3. 处理中间重叠的区间
        // 按 start 升序排序
        node->by_start = overlaps;
        sort(node->by_start.begin(), node->by_start.end(), [](const Interval& a, const Interval& b) {
            return a.start < b.start;
        });

        // 按 end 降序排序 (便于 t > center 时快速截断)
        node->by_end = overlaps;
        sort(node->by_end.begin(), node->by_end.end(), [](const Interval& a, const Interval& b) {
            return a.end > b.end;
        });

        // 4. 递归构建左右子树
        // 注意：防止死循环，如果区间全部聚在中间，则不再递归
        if (!lefts.empty()) node->left = build(lefts);
        if (!rights.empty()) node->right = build(rights);

        return node;
    }

    // 递归查询
    void query(Node* node, int t, vector<int>& results) {
        if (!node) return;

        if (t < node->center) {
            // 情况 1: 查询时间在中心点左侧
            // 检查重叠区：因为这些区间都覆盖 center，即 end >= center > t 必然成立
            // 我们只需要找 start <= t 的区间
            for (const auto& i : node->by_start) {
                if (i.start > t) break; // 因为是升序，后面的肯定也不满足，直接 break 剪枝
                results.push_back(i.id);
            }
            // 继续去左子树找
            query(node->left, t, results);
        } 
        else if (t > node->center) {
            // 情况 2: 查询时间在中心点右侧
            // 检查重叠区：因为这些区间都覆盖 center，即 start <= center < t 必然成立
            // 我们只需要找 end >= t 的区间
            for (const auto& i : node->by_end) {
                if (i.end < t) break; // 因为是降序，后面的肯定更小，直接 break 剪枝
                results.push_back(i.id);
            }
            // 继续去右子树找
            query(node->right, t, results);
        } 
        else {
            // 情况 3: t == center
            // 所有重叠区间的区间都包含 center，直接全部加入
            for (const auto& i : node->by_start) {
                results.push_back(i.id);
            }
            // 不需要查左右子树了，因为左子树 end < center，右子树 start > center
        }
    }

public:
    // 构造函数：接收原始数据并预处理
    IntervalTree(const vector<pair<int, int>>& raw_ranges) {
        vector<Interval> intervals;
        for (int i = 0; i < raw_ranges.size(); ++i) {
            intervals.push_back({raw_ranges[i].first, raw_ranges[i].second, i});
        }
        root = build(intervals);
    }

    ~IntervalTree() {
        delete root;
    }

    // 对外接口
    vector<int> search(int timestamp) {
        vector<int> results;
        query(root, timestamp, results);
        // 题目要求的输出顺序往往是索引顺序，如果需要排序可以在这里 sort
        sort(results.begin(), results.end()); 
        return results;
    }
};

int main() {
    // 测试数据
    vector<pair<int, int>> ranges = {
        {0, 5},
        {6, 8},
        {2, 9},
        {4, 10},
        {3, 5}
    };

    // 1. 预处理数据 (Build)
    IntervalTree tree(ranges);

    // 2. 执行查询
    int query_time = 3;
    vector<int> result = tree.search(query_time);

    // 输出结果
    cout << "Users active at time " << query_time << ": [ ";
    for (int id : result) {
        cout << id << " ";
    }
    cout << "]" << endl;

    return 0;
}

比较两棵树中序遍历结果是否一致

class Solution {
public:
    bool isSameInorderSequence(TreeNode* root1, TreeNode* root2) {
        stack<TreeNode*> st1, st2;
        
        while (root1 != nullptr || !st1.empty() || root2 != nullptr || !st2.empty()) {
            // 1. 尽可能向左走，把沿途节点压入栈中
            while (root1 != nullptr) {
                st1.push(root1);
                root1 = root1->left;
            }
            while (root2 != nullptr) {
                st2.push(root2);
                root2 = root2->left;
            }

            // 2. 检查结构：如果此时一个栈为空而另一个不为空，说明节点数量或结构不一致
            if (st1.empty() || st2.empty()) {
                return false; 
            }

            // 3. 取出当前节点（中序遍历到的节点）
            root1 = st1.top(); st1.pop();
            root2 = st2.top(); st2.pop();

            // 4. 比较数值：如果不相等，直接返回 false
            if (root1->val != root2->val) {
                return false;
            }

            // 5. 转向右子树
            root1 = root1->right;
            root2 = root2->right;
        }

        return true;
    }
};