[leetcode]Binary Tree Level Order Traversal II by c++

Binary Tree Level Order Traversal II by c++

原题&翻译

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).

给出一颗二叉树,返回倒序的层级遍历各节点值。(另外,从左到右,从叶子到根一级一级的遍历)

比如 : 给出这样一颗树,[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回的倒序层级遍历应该是:

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

解题思路

一般解法

先得到树的最大深度,并且生成等长的二维数组 result。然后就是递归遍历,并且保存了。

class Solution {
public:
    vector<vector<int>> result;

    int depth(TreeNode *root) {
        if (!root) return 0;
        return max(depth(root->left),depth(root->right))+1;
    }

    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        int d = depth(root);

        for(int i=0;i<d;i++){
            result.push_back(vector<int>());
        }

        levelTree(root, d-1);

        return result;
    }

    void levelTree(TreeNode* root, int levels) {
        if (!root) return;

        result[levels].push_back(root->val);

        levelTree(root->left, levels - 1 );

        levelTree(root->right, levels - 1);
    }
};

解法二

这是抄过来的解法,是顺序得到结果,然后逆序输出,时间上反而少一点。

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> list={};
        dfs(list,root,1);
        reverse(list.begin(),list.end());
        return list;
    }

    void dfs(vector<vector<int>> &list, TreeNode * root, int depth){
        if(root==NULL)
            return;
        if(list.size()<depth)
            list.resize(depth);
        list[depth-1].push_back(root->val);

        dfs(list,root->left,depth+1);
        dfs(list,root->right,depth+1);
    }
};