【Leetcode】【Easy】Binary Tree Level Order Traversal-白红宇

【Leetcode】【Easy】Binary Tree Level Order Traversal

阅读量：4583 次

发布时间：2019-06-09

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

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,#,#,15,7},

3   / \  9  20    /  \   15   7

return its level order traversal as:

[  [3],  [9,20],  [15,7]]

BFS解题思路：

使用二叉树按层遍历的方法，很容易解决。

1 /** 2  * Definition for binary tree 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         vector
       
        
          > levelOrderLst;14         vector
         
           valLst;15         queue
          
            curLevelNodes;16 17 if (!root)18 return levelOrderLst;19 20 curLevelNodes.push(root);21 22 while (!curLevelNodes.empty()) {23 int len = curLevelNodes.size();24 while (len--) {25 valLst.push_back(curLevelNodes.front()->val); 26 27 if (curLevelNodes.front()->left) {28 curLevelNodes.push(curLevelNodes.front()->left);29 }30 31 if (curLevelNodes.front()->right) {32 curLevelNodes.push(curLevelNodes.front()->right);33 }34 35 curLevelNodes.pop();36 }37 38 levelOrderLst.push_back(valLst);39 valLst.clear();40 }41 42 return levelOrderLst;43 44 }45 46 };

DFS解题思路：

[                 [  [3],              [3],  [9],   ==>        [9,20],  [15]              [15,7]]                 ]

树中，第一层val值保存在vec[0]，第N层val值保存在vec[n-1]。因此按DFS原则，可以统一使用“先左后右”的规律，先遍历左子树，再遍历右子树。遍历到的val值插入对应dep的位置中。

注意：将val插入对应dep位置前，此位置上需要存在子列表，才能执行插入命令（代码中10-11行）。

1 class Solution { 2 private: 3     vector
     
      
        > levelOrderLst; 4 public: 5     void buildVector(TreeNode *root, int depth) 6     { 7         if (root == NULL) 8             return; 9             10         if (levelOrderLst.size() == depth)11             levelOrderLst.push_back(vector
       
        ());12             13         levelOrderLst[depth].push_back(root->val);14         15         buildVector(root->left, depth + 1);16         buildVector(root->right, depth + 1);17     }18     19     vector
        
         
           > levelOrder(TreeNode *root) {20         buildVector(root, 0);21         return levelOrderLst;22     }23 };