LeetCode 102. Binary Tree Level Order Traversal 和107

LeetCode102. Binary Tree Level Order Traversal

题目链接：https://leetcode.com/PRoblems/binary-tree-level-order-traversal/?tab=Description

题目描述：

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:Given binary tree [3,9,20,null,null,15,7],

    3   / /  9  20    /  /   15   7
return its level order traversal as:
[  [3],  [9,20],  [15,7]]
思路一：用深度优先搜索（DFS），遍历的同时记录深度，将深度相同的插入到结果中，用时6ms
/** * 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;        DFS(root,result,-1);        return result;        }    void DFS(TreeNode* curNode,vector<vector<int>>& result,int curLevel)    {        if(curNode==NULL)            return;        curLevel++;        if(result.size()<curLevel+1)        {            vector<int> tmp;            tmp.push_back(curNode->val);            result.push_back(tmp);        }        else            result[curLevel].push_back(curNode->val);        DFS(curNode->left,result,curLevel);        DFS(curNode->right,result,curLevel);    }};
思路二：用广度优先遍历（BFS），记录每一层的size，将每一层插入到结果中，用时3ms
/** * 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==NULL)            return result;        queue<TreeNode*> q;        q.push(root);        while(!q.empty())        {            int s=q.size();            vector<int> inner;            while(s--)            {                TreeNode* tmp=q.front();                inner.push_back(tmp->val);                if(tmp->left!=NULL)                    q.push(tmp->left);                if(tmp->right!=NULL)                    q.push(tmp->right);                q.pop();            }            result.push_back(inner);        }        return result;    }};
LeetCode107. Binary Tree Level Order Traversal II
题目链接：https://leetcode.com/problems/binary-tree-level-order-traversal-ii/?tab=Description
题目描述:
Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
For example:Given binary tree [3,9,20,null,null,15,7],
    3   / /  9  20    /  /   15   7
return its bottom-up level order traversal as:
[  [15,7],  [9,20],  [3]]
思路：此题可以直接用上一题的方法，将结果逆序即可，也可将每一层在结果中插入的时候，一直在最前面插入
/** * 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>> levelOrderBottom(TreeNode* root) {    vector<vector<int>> result;        if(root==NULL)            return result;        queue<TreeNode*> q;        q.push(root);        while(!q.empty())        {            int s=q.size();            vector<int> inner;            while(s--)            {                TreeNode* tmp=q.front();                inner.push_back(tmp->val);                if(tmp->left!=NULL)                    q.push(tmp->left);                if(tmp->right!=NULL)                    q.push(tmp->right);                q.pop();            }            //result.insert(result.begin(),inner);            result.push_back(inner);        }        reverse(result.begin(), result.end());        return result;    }};