Q:
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
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] ]
A:
----------------dfs ------------recursive way -----------------/** * 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: vector<vector<int>> levelOrderBottom(TreeNode* root) { vector<vector<int>> res; int d = getDepth(root); for(int i =0;i<d; i++) { vector<int> tmp; res.push_back(tmp); } helper(root, res, d-1); return res; } private: int getDepth(TreeNode* const root) { if(!root) return 0; return 1 + max(getDepth(root->left), getDepth(root->right)); } void helper(TreeNode* const root, vector<vector<int>> &res, int layer) { if(!root) return ; helper(root->left, res, layer-1); helper(root->right, res, layer-1); res[layer].push_back(root->val); } };
Mistakes:
1: 忘了是bottom-up,因此需要height - 1 - level------------------BFS ------记住当前一层的TreeNode---------iterative way -----------
除了方法名不一样以外, 只在shrink2int方法的最后, 把newAll.add(newAl) 改成newAll.add(0, newAl)----- 即可-------
public class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { List<List<Integer>> all = new LinkedList<List<Integer>>(); if(root == null) return all; List<TreeNode> curList = new LinkedList<TreeNode>(); curList.add(root); while( !curList.isEmpty()){ List<TreeNode> newList = new LinkedList<TreeNode>(); List<Integer> thisLevel = new LinkedList<Integer>(); while(curList.isEmpty()==false){ TreeNode cur = curList.remove(0); thisLevel.add(cur.val); if(cur.left!=null) newList.add(cur.left); if(cur.right!=null) newList.add(cur.right); } all.add(0,thisLevel); curList = newList; } return all; } }
No comments:
Post a Comment