Algorithm

Binary Tree iteration

递åŊ’遍历

//前åēéåŽ†
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);
    }
}

非递åŊ’遍历 Reference: 更įŽ€å•įš„非递åŊ’遍历äēŒå‰æ ‘įš„æ–šæŗ•

非递åŊ’遍历äēŒå‰æ ‘åŽžé™…ä¸Šå°ąæ˜¯įœ‹æ˜¯åĻįŦŦäēŒæŦĄéåŽ†īŧŒįŦŦäēŒæŦĄéåŽ†įš„æ—ļ候加å…Ĩ到įģ“果集合中åŗ可īŧŒæŒ‰į…§čŋ™ä¸Ē思æƒŗå°ąå¯äģĨ借劊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));
        }
    }
}

DFS & BFS

https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/bfs-de-shi-yong-chang-jing-zong-jie-ceng-xu-bian-l/

Last updated