首页 > 代码库 > [Leetcode][Tree][Binary Tree Level Order Traversal ]

[Leetcode][Tree][Binary Tree Level Order Traversal ]

2024-07-10 03:09:57   218人阅读

树的层次遍历，比较简单，3个题的做法完全一样，只是在特定的地方对结果进行reverse。

 

1、Binary Tree Level Order Traversal

/** * Definition for binary tree * 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;        vector<TreeNode *> levelNodes;        if (root == NULL) {            return result;        }        levelNodes.push_back(root);        while (levelNodes.size() > 0) {            vector<TreeNode *> nextLevelNodes;            vector<int> levelVals;            for (int i = 0; i < levelNodes.size(); i++) {                levelVals.push_back(levelNodes[i]->val);                if (levelNodes[i]->left != NULL) {                    nextLevelNodes.push_back(levelNodes[i]->left);                }                if (levelNodes[i]->right != NULL) {                    nextLevelNodes.push_back(levelNodes[i]->right);                }            }            result.push_back(levelVals);            levelNodes = nextLevelNodes;        }        return result;    }};

　2、 Binary Tree Level Order Traversal II

/** * Definition for binary tree * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    vector<vector<int> > levelOrderBottom(TreeNode *root) {        vector<vector<int> > result;        vector<TreeNode *> levelNodes;        if (root != NULL) {            levelNodes.push_back(root);        }        while (levelNodes.size() > 0) {            vector<TreeNode *> next;            vector<int> nodeValues;            for (int i = 0; i < levelNodes.size(); i++) {                nodeValues.push_back(levelNodes[i]->val);                if (levelNodes[i]->left != NULL) {                    next.push_back(levelNodes[i]->left);                }                if (levelNodes[i]->right != NULL) {                    next.push_back(levelNodes[i]->right);                }            }            result.push_back(nodeValues);            levelNodes = next;        }        reverse(result.begin(), result.end());        return result;    }};

　3、Binary Tree Zigzag Level Order Traversal

/** * Definition for binary tree * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    vector<vector<int> > zigzagLevelOrder(TreeNode *root) {        vector<vector<int> > result;        vector<TreeNode *> nodes;        if (root != NULL) {            nodes.push_back(root);        }        bool flag = false;        while (nodes.size() > 0) {            vector<TreeNode *> next;            vector<int> values;            for (int i = 0; i < nodes.size(); i++) {                values.push_back(nodes[i]->val);                if (nodes[i]->left != NULL) {                    next.push_back(nodes[i]->left);                }                if (nodes[i]->right != NULL) {                    next.push_back(nodes[i]->right);                }            }            if (flag) {                reverse(values.begin(), values.end());            }            result.push_back(values);            nodes = next;            flag = !flag;        }        return result;    }};

　　

 

 


联系
我们