Leetcode 102.Binary Tree Level Order Traversal

原题地址：https://leetcode.com/problems/binary-tree-level-order-traversal/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]，
return its zigzag level order traversal as:
[ [3], [9,20], [15,7] ]

即由上到下由左到右把每一层的节点值放在一个vector<int>里，最后返回一个大的vector<vector<int>>

解题思路

和上一题很像，用深度优先遍历，在深度优先里递归左子节点再递归右子节点。创建一个变量deepest保存目前最大深度，同时遍历的时候记录当前深度，如果当前深度比最大深度更大，就更新最大深度，同时创建一个新的vector<int>放到vector<vector<int>>末尾，并把当前节点的值放入那个新的vector<int>的末尾。

代码

/**
 * 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:
    int deepest = 0;
    vector<vector<int> > result;
    
    void DFS(TreeNode* root,int current_level){
        if(root==NULL){
            return ;
        }
        current_level++;
        if(current_level > deepest){
            deepest=current_level;
            vector<int> temp;
            result.push_back(temp);
        }
        result[current_level-1].push_back(root->val);
        DFS(root->left,current_level);
        DFS(root->right,current_level);
    }
    
    vector<vector<int>> levelOrder(TreeNode* root) {
       DFS(root,0);
        return result;
    }
};

TIM截图20170918151604.png