二叉树的遍历
二叉树的遍历：
三种递归遍历:
//前序遍历
void preorder(TreeNode *root, vector<int> &path)
{
if(root != NULL)
{
path.push_back(root->val);
preorder(root->left, path);
preorder(root->right, path);
}
}
//中序遍历
void inorder(TreeNode *root, vector<int> &path)
{
if(root != NULL)
{
inorder(root->left, path);
path.push_back(root->val);
inorder(root->right, path);
}
}
//后续遍历
void postorder(TreeNode *root, vector<int> &path)
{
if(root != NULL)
{
postorder(root->left, path);
postorder(root->right, path);
path.push_back(root->val);
}
}
非递归：
//非递归前序遍历
void preorderTraversal(TreeNode *root, vector<int> &path){
stack<TreeNode *> s;
TreeNode *p = root;
while(p != NULL || !s.empty())
{
while(p != NULL)
{
path.push_back(p->val);
s.push(p);
p = p->left;
}
if(!s.empty())
{
p = s.top();
s.pop();
p = p->right;
}
}
}
//非递归中序遍历
void inorderTraversal(TreeNode *root, vector<int> &path){
stack<TreeNode *> s;
TreeNode *p = root;
while(p != NULL || !s.empty())
{
while(p != NULL)
{
s.push(p);
p = p->left;
}
if(!s.empty())
{
p = s.top();
path.push_back(p->val);
s.pop();
p = p->right;
}
}
}
后序非递归遍历：
vector<int> postorderTraversal(TreeNode* root) {
vector<int> v;
if(root==nullptr)
return v;
stack<TreeNode*> s;
TreeNode *cur=root;
TreeNode *pre=nullptr; //修改1，增加指向前一结点的指针
while(cur || !s.empty()){
while(cur){
s.push(cur);
cur=cur->left;
}
cur=s.top();
if(cur->right==nullptr || cur->right==pre){ //修改二，增加判断是否该输出结点
v.push_back(cur->val);
s.pop();
pre=cur;
cur=nullptr;
}
else
cur=cur->right;
}
return v;
}
//层次遍历：如果不需要确定当前遍历到了哪一层，模板如下：
vector<int> PrintFromTopToBottom(TreeNode* root) {
vector<int> ret;
if (!root) return ret;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode *node = q.front();
q.pop();
ret.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
return ret;
}
//如果需要知道到了那一层，代码如下：
vector<int> PrintFromTopToBottom(TreeNode* root) {
int level=0;
vector<int> ret;
if (!root) return ret;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int sz=q.size();
while(sz--){
TreeNode *node = q.front();
q.pop();
ret.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
level++;
}
return ret;
}
作者：xyTen
链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/er-cha-shu-hou-xu-fei-di-gui-bian-li-liang-chong-z/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
vector<TreeNode*> s;
int sum=0;
vector<vector<int> > v1;
vector<int> v2;
if(root==nullptr) return v1;
TreeNode* cur =root;
TreeNode* pre =nullptr;
while(cur!=nullptr || !s.empty()){
while(cur!=nullptr){
s.push_back(cur);
v2.push_back(cur->val);
sum+=cur->val;
cur=cur->left;
}
cur=s.back();
if(cur->right==nullptr || cur->right==pre){
if(cur->left==nullptr && cur->right==nullptr && sum==expectNumber){
v1.push_back(v2);
}
s.pop_back();
pre=cur;
sum-=cur->val;
v2.pop_back();
cur=nullptr;
}
else{
cur=cur->right;
}
}
return v1;
}给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void mid(TreeNode* p,int a,int &b){
if(p!=nullptr){
a+=1;
if(b==0 && p->right==nullptr && p->left==nullptr){
b=a;
}
else if(b!=0 && p->right==nullptr && p->left==nullptr){
if(a<b){
b=a;
}
}
mid(p->left,a,b);
mid(p->right,a,b);
}
}
int minDepth(TreeNode* root) {
int a=0;
int b=0;
mid(root,a,b);
return b;
}
};
