LeetCode 102. 二叉树的层次遍历-白红宇

LeetCode 102. 二叉树的层次遍历

阅读量：4593 次

发布时间：2019-06-09

本文共 1888 字，大约阅读时间需要 6 分钟。

给定一个二叉树，返回其按层次遍历的节点值。（即逐层地，从左到右访问所有节点）。

例如:

给定二叉树: [3,9,20,null,null,15,7],

/ \

9 20

/ \

15 7

返回其层次遍历结果：

[

[3],

[9,20],

[15,7]

]

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal

递归：

/** * 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:    void process(TreeNode* root,int depth,vector
     
      
       > &ans)    {        if(depth >= ans.size())            ans.push_back(vector
       
         {});        ans[depth].push_back(root->val);        if(root->left) process(root->left,depth+1,ans);        if(root->right) process(root->right,depth+1,ans);    }    vector
        
         
          > levelOrder(TreeNode* root) {        vector
          
           
            > ans; if(root) process(root,0,ans); return ans; } };

非递归：

1 /** 2  * Definition for a binary tree node. 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     vector
     
      
       > levelOrder(TreeNode* root) {13         14         vector
       
        
         > ans;15         if(!root) return ans;16 17         queue
         
           Q;18         TreeNode* temp;19         Q.push(root);20         while (!Q.empty()){21             vector
          
            ress;22 int n = Q.size();23 for(int i = 0; i < n; i++) {24 temp = Q.front();25 ress.push_back(temp->val);26 Q.pop();27 if(temp->left)28 Q.push(temp->left);29 if(temp->right)30 Q.push(temp->right);31 }32 ans.push_back(ress);33 }34 return ans;35 }36 };