面试题32:从上到下打印二叉树

从上到下打印二叉树

题目描述leetcodeleetcode 二叉树的层次遍历 IIleeched 二叉树的层平均值

题目描述

不分行从上到下打印二叉树

利用队列，打印当前节点时，应将该节点的孩子节点放入队列中。每次取队首元素进行打印

分行从上到下打印？

加入分行的标志节点，一个变量表示当前的节点数，另一个表示下层节点数

void PrintTree(BinaryTreeNode *pRoot) { if(pRoot == nullptr) return; queue<BinaryTreeNode *>nodes; nodes.push(pRoot); int nextLevel = 0; int toBePrint = 1; while(!nodes.empty()) { BinaryTreeNode *pNode = nodes.front(); cout<<pNode->val<<" "; if(pNode->left !=nullptr) { nodes.push(pNode->left); nextLevel ++; } if(pNode->right != nullptr) { nodes.push(pNode->right); nextLevel++; } nodes.pop(); toBePrint--; if(toBePrint == 0) { cout<<endl; tiBePrint = nextLevel; nextLevel = 0; } } }

leetcode

二叉树的层次遍历 给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。 /** * 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>> levelOrder(TreeNode* root) { vector<vector<int>>res; if(root ==nullptr) return res; vector<int>nodes; queue<TreeNode *>record; record.push(root); int currentlevel = 1; int nextlevel = 0; while(!record.empty()) { TreeNode *Node = record.front(); nodes.push_back(Node->val); if(Node->left!=nullptr) { record.push(Node->left); nextlevel ++; } if(Node->right !=nullptr) { record.push(Node->right); nextlevel++; } record.pop(); currentlevel--; if(currentlevel == 0) { currentlevel = nextlevel; nextlevel = 0; res.push_back(nodes); nodes.clear(); } } return res; } };

执行用时 : 12 ms, 在Binary Tree Level Order Traversal的C++提交中击败了95.17% 的用户 内存消耗 : 13.9 MB, 在Binary Tree Level Order Traversal的C++提交中击败了50.53% 的用户

leetcode 二叉树的层次遍历 II

二叉树的层次遍历 II 给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

只需要把上面代码改一句res的插入位置即可

/** * 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; if(root ==nullptr) return res; vector<int>nodes; queue<TreeNode *>record; record.push(root); int currentlevel = 1; int nextlevel = 0; while(!record.empty()) { TreeNode *Node = record.front(); nodes.push_back(Node->val); if(Node->left!=nullptr) { record.push(Node->left); nextlevel ++; } if(Node->right !=nullptr) { record.push(Node->right); nextlevel++; } record.pop(); currentlevel--; if(currentlevel == 0) { currentlevel = nextlevel; nextlevel = 0; res.insert(res.begin(), nodes); nodes.clear(); } } return res; } };

执行用时 : 20 ms, 在Binary Tree Level Order Traversal II的C++提交中击败了64.92% 的用户 内存消耗 : 14.1 MB, 在Binary Tree Level Order Traversal II的C++提交中击败了30.31% 的用户

leeched 二叉树的层平均值

二叉树的层平均值 给定一个非空二叉树, 返回一个由每层节点平均值组成的数组.

同样，修改条件即可

/** * 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<double> averageOfLevels(TreeNode* root) { vector<double>res; if(root ==nullptr) return res; double sum = 0.0; queue<TreeNode *>record; record.push(root); double avg = 0.0; int currentlevel = 1; int count = 1; int nextlevel = 0; while(!record.empty()) { TreeNode *Node = record.front(); sum += Node->val; if(Node->left!=nullptr) { record.push(Node->left); nextlevel ++; } if(Node->right !=nullptr) { record.push(Node->right); nextlevel++; } record.pop(); currentlevel--; if(currentlevel == 0) { currentlevel = nextlevel; nextlevel = 0; avg = sum / count; res.push_back(avg); avg = 0.0; sum =0.0; count = currentlevel; } } return res; } };