当前位置 博文首页 > Scissors_初夏的博客:初夏小谈:LC.107:二叉树的层序遍历
题目描述:
给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
例如:
给定二叉树?[3,9,20,null,null,15,7]
,3 / \ 9 20 / \ 15 7返回其自底向上的层次遍历为:
[ [15,7], [9,20], [3] ]解题思路:
在进行层序遍历时,用一个队列的话无法确定其中的结点到底是那一层的,既然一个无法确定两个了,一个保存结点,一个保存它的层数。每当取一个结点就把它的数据放进一个二维数组中,二维数组的行用来表示层数。通过第二个队列得知。然后把该节点的左右孩子在拉进这个队列。对应记录左右孩子结点的层数。然后再取孩子重复上述操作。
注意:
对于vector构成的二维数组要进行resize,不然不能直接对空间进行解引用,否则直接崩溃。
cs代码实现:
/** * 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) { queue<TreeNode*> NodePtr; //保存结点 queue<int> Level; //保存数据结点的层数 vector<vector<int>> vi; //保存结点中的数据 //把结点压进第一个队列中 if(root) { NodePtr.push(root); Level.push(1); } //设置容量防止对无效指针进行解引用 vi.resize(TreeHeight(root)); //只要有节点就一直出,出完,就把它的左右孩子拉进去第一个队列 while(!NodePtr.empty()) { TreeNode* Node = NodePtr.front(); NodePtr.pop(); int count = Level.front(); Level.pop(); vi[count - 1].push_back(Node->val); if(Node->left) { NodePtr.push(Node->left); Level.push(count + 1); } if(Node->right) { NodePtr.push(Node->right); Level.push(count + 1); } } reverse(vi.begin(), vi.end()); return vi; } //求二叉树的高度目的是设置vector<vector<int>>的大小 int TreeHeight(TreeNode* root) { if(root == NULL) { return 0; } int LeftHeight = TreeHeight(root->left); int RightHeight=TreeHeight(root->right); return LeftHeight > RightHeight ? LeftHeight + 1 : RightHeight + 1; } };
运行结果:
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?珍&源码
下一篇:没有了