六、树 🌴

• 六、树 🌴
  • 最近公共祖先
  • 二叉树
  • BFS

最近公共祖先

• 【2096（周赛）】
  • 基本思想：先找 root 到两个节点的路径，然后删除 root 到最近公共祖先的路径，一边全部替换成 U，然后两段路径拼接。
  • 小技巧：维护了树的父节点哈希表

二叉树

• 【2196. 根据描述创建二叉树（周赛）】

BFS

模板

        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty())
        {
            int size = q.size();
            for(int i=0;i<size;i++)
            {
                auto node =q.front();
                q.pop();
                if(node->left)
                    q.push(node->left);
                if(node->right)
                    q.push(node->right);
            }
        }