【剑指offer】之层次遍历

小鱼儿 2023-06-24 10:28 37阅读 0赞

**题目描述**  
从上往下打印出二叉树的每个节点，同层节点从左至右打印。  
思路：层次遍历树，说到数组的根节点和左右子节点的关系，每个第i个节点，他的第2i和2i+1就是他们的子节点。所以每次打印的顺序就定了下来，根一节点，根二节点，根一节点左，右节点。根二节点的左右节点。  
所以根据这个顺序，我们可以利用一个数据结构，来依照此存入节点。  
可以用list，也可以用duque，队列。

先压入第一个，并且打印，如果左右节点还有，就压入队列，然后弹出第一个（已经打印），判断此时的队列是否为空，条件就是这个，当队列为空，代表没有了节点。

代码：

class Solution { //1内存超限制错误！陷入死循环，以根节点来压入弹出，而不是以队列的首节点。2.左右顺序有错(多处）)
    public://思路：用一个辅助队列来保存每一个节点然后压入子节点，弹出父节点
        vector<int> PrintFromTopToBottom(TreeNode* root) { 
            vector<int> res;
            if(root==nullptr)    return res;
            deque<TreeNode*> node;
            node.push_back(root);
            while(node.size())
            { 
                res.push_back(node.front()->val);        //访问val是一个指针不是一个对象
                if(node.front()->left)    node.push_back(node.front()->left);        //错误：是排在首位的元素来查询是否需要把其子树压入
                if(node.front()->right)     node.push_back(node.front()->right);    //使用的是root，那么一直压入根节点的左右子节点，一直循环
                node.pop_front();        //不需要了，弹
                
            }
            return res;
        }
    };