首页 > 代码库 > Binary Tree Level Order Traversal

Binary Tree Level Order Traversal

2024-09-11 23:59:04   209人阅读

思路一：使用非递归方式，当时还是需要注意每当一个算法写完后，检查是否处理到根节点或者list为空的情况

/**
 * 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>> result;
        if(root == nullptr)
            return result;
        stack<TreeNode *> s;
        
        s.push(root);
        while(!s.empty())
        {
            vector<TreeNode *> tmp;
            vector<int> _result;
            while(!s.empty())
            {
                _result.push_back(s.top()->val);
                tmp.push_back(s.top());
                s.pop();
            }
            result.push_back(_result);
            
            for(int i=tmp.size()-1; i >= 0; --i)
            {
                if(tmp[i]->right != nullptr)
                    s.push(tmp[i]->right);
                if(tmp[i]->left != nullptr)
                    s.push(tmp[i]->left);
            }
        }
        
        return result;
    }
};

思路二：采用递归的方式，这里使用一个额外参数记录了层次遍历的深度

/**
 * 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>> result;
        
        tranverse(root, 1, result);
        return result;
    }
    
    void tranverse(TreeNode *root, int level, vector<vector<int>> &result)
    {
        if(root == nullptr)
            return;
            
        if(level > result.size())
            result.push_back(vector<int>());
        result[level-1].push_back(root->val);
        
        if(root->left != nullptr)
            tranverse(root->left, level+1, result);
        if(root->right != nullptr)
            tranverse(root->right, level+1, result);
    }
};

 

Binary Tree Level Order Traversal


联系
我们