//ๅๅบ้ๅ
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);
}
}
้้ๅฝ้ๅไบๅๆ ๅฎ้
ไธๅฐฑๆฏ็ๆฏๅฆ็ฌฌไบๆฌก้ๅ๏ผ็ฌฌไบๆฌก้ๅ็ๆถๅๅ ๅ
ฅๅฐ็ปๆ้ๅไธญๅณๅฏ๏ผๆ็
ง่ฟไธชๆๆณๅฐฑๅฏไปฅๅๅฉstack็ๅ
่ฟๅ
ๅบๆงๅถๆ ็็ป็น็้ๅ๏ผ
//ๆด็ฎๅ็้้ๅฝๅๅบ้ๅ
void preorderTraversalNew(TreeNode *root, vector<int> &path)
{
stack< pair<TreeNode *, bool> > s;
s.push(make_pair(root, false));
bool visited;
while(!s.empty())
{
root = s.top().first;
visited = s.top().second;
s.pop();
if(root == NULL)
continue;
if(visited)
{
path.push_back(root->val);
}
else
{
s.push(make_pair(root->right, false));
s.push(make_pair(root->left, false));
s.push(make_pair(root, true));
}
}
}
//ๆด็ฎๅ็้้ๅฝไธญๅบ้ๅ
void inorderTraversalNew(TreeNode *root, vector<int> &path)
{
stack< pair<TreeNode *, bool> > s;
s.push(make_pair(root, false));
bool visited;
while(!s.empty())
{
root = s.top().first;
visited = s.top().second;
s.pop();
if(root == NULL)
continue;
if(visited)
{
path.push_back(root->val);
}
else
{
s.push(make_pair(root->right, false));
s.push(make_pair(root, true));
s.push(make_pair(root->left, false));
}
}
}
//ๆด็ฎๅ็้้ๅฝๅๅบ้ๅ
void postorderTraversalNew(TreeNode *root, vector<int> &path)
{
stack< pair<TreeNode *, bool> > s;
s.push(make_pair(root, false));
bool visited;
while(!s.empty())
{
root = s.top().first;
visited = s.top().second;
s.pop();
if(root == NULL)
continue;
if(visited)
{
path.push_back(root->val);
}
else
{
s.push(make_pair(root, true));
s.push(make_pair(root->right, false));
s.push(make_pair(root->left, false));
}
}
}
https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/bfs-de-shi-yong-chang-jing-zong-jie-ceng-xu-bian-l/