letecode [107] - Binary Tree Level Order Traversal II
发布时间:2020-12-14 04:44:45 所属栏目:大数据 来源:网络整理
导读: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,15,7], ??? 3 ?? / ? 9? 20 ??? /? ?? 15?? 7 ? re
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,15,7], ??? 3 ?? / ? 9? 20 ??? /? ?? 15?? 7
?
return its bottom-up level order traversal as:
[ ? [15, ? [9,20], ? [3] ]
?
题目大意: 给定一个二叉树,输出它层次遍历的结果,该结果用二维向量表示,向量每个元素为当前层从左到右的节点集合,且从叶节点向上存放。 理? 解 : 需要注意的是,没遍历一层二叉树时,需要用vector保存这些节点,其次,这些节点在二维vector里从叶节点向上存放的,但遍历二叉树是从上往下的。 我的做法是:先遍历二叉树的深度,获得层数,即元素个数。遍历时,从根节点层开始,同时给二维vector从最后一个元素开始赋值。 用队列作为辅助,每遍历一层,获得当层元素个数,便于用vector保存这些元素。并将当前层所有节点的非空孩子节点加入队列。 当队列为空,即遍历结束。 也可以,不先获取二叉树深度。直接每访问一层并存放,遍历完二叉树后,逆置二维vector即可。 代 码 C++: /** * 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 getDepth(TreeNode* root){ if(root==NULL) return 0; if(root->left==NULL && root->right==NULL) return 1; int left = getDepth(root->left); int right = getDepth(root->right); return left>right? left+1:right+1; } vector<vector<int>> levelOrderBottom(TreeNode* root) { vector<vector<int>> vec; if(root==NULL) return vec; int depth = getDepth(root); vec.resize(depth); vector<int> childVec; queue<TreeNode*> q; int childSize; TreeNode* node; q.push(root); while(q.empty()!=true){ childSize = q.size(); while(childSize>0){ node = q.front(); childVec.push_back(node->val); q.pop(); if(node->left!=NULL) q.push(node->left); if(node->right!=NULL) q.push(node->right); --childSize; } vec[depth-1] = childVec; childVec.clear(); depth--; } return vec; } }; ? 运行结果: 执行用时 :?16 ms 内存消耗 :?13.8 MB (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |