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

Was this helpful?