【LeetCode】107. Binary Tree Level Order Traversal II

问题描述

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]
]

层次遍历，但要求从叶子到根保存树的节点值。

问题分析

首先求出树的深度作为初始层次，然后从根节点开始遍历树，首先遍历节点的左子树和右子树，最后再将节点值添加到对应层次的数组中。

算法描述：

level = 树的深度
r = 数组[level]
遍历树(指针p，层次level)
  如果p为空，返回
  遍历左子树（p->left, level-1）
  遍历右子树（p->right，level-1）
  存储值 r[level].push(p->val)

代码

class Solution {
public:
    vector<vector<int> > levelOrderBottom(TreeNode* root) {
        int level = depth(root, 0);
        vector<vector<int> > r(level);
        fun(root, r, level-1);
        return r;
    }
    
    int depth(TreeNode* p, int level) {
        if(p==0) return level;
        level++;
        int l1 = depth(p->left, level);
        int l2 = depth(p->right, level);
        return l1>l2?l1:l2;
    } 
    
    void fun(TreeNode* p, vector<vector<int> > &r, int level) {
    	if(p==0||level<0) return;
	    fun(p->left, r, level-1);
	    fun(p->right, r, level-1);
	    r[level].push_back(p->val);
    }
};