leetcode102. 二叉树的层次遍历

短命女 2023-07-05 10:25 17阅读 0赞

### 解题思路 ###

难点是记录层的最后一个节点。  
思路：在还未到达该层的最后一个节点前，提前记录下一层的最后一个节点

### 代码 ###

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
    class Solution { 
    public:
        vector<vector<int>> levelOrder(TreeNode* root) { 
            vector< vector<int> > ans;
            if(root==NULL) return ans;
            queue<TreeNode*> que;
            int last=root->val;
            que.push(root);
            vector<int> tm;
            TreeNode* pre=root;
            TreeNode* newPre=NULL;
            //TreeNode* isr=root;
            int newLast=0;
            while(que.empty()==0)
            { 
                
                TreeNode *tmp=que.front();
                que.pop();
                tm.push_back(tmp->val);
                if(tmp->left)
                { 
                    newLast=tmp->left->val;
                    newPre=tmp->left;
                }
                if(tmp->right)
                { 
                    newLast=tmp->right->val;
                    newPre=tmp->right;
                }
                if(tmp->val==last&&tmp==pre)
                { 
                   // cout<<newLast<<endl;
                    last=newLast;
                    pre=newPre;
                    ans.push_back(tm);
                    tm.clear();
                }
                if(tmp->left)
                { 
                    que.push(tmp->left);
                }
                if(tmp->right) que.push(tmp->right);
    
            }
            if(tm.empty()==0)
            { 
                ans.push_back(tm);
            }
            //ans.push_back(tm);
            return ans;
        }
    };