C++實現(xiàn)LeetCode(144.二叉樹的先序遍歷)

更新時間：2021年07月15日 10:18:49 作者：Grandyang

這篇文章主要介紹了C++實現(xiàn)LeetCode(144.二叉樹的先序遍歷),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

[LeetCode] 144. Binary Tree Preorder Traversal 二叉樹的先序遍歷

Given a binary tree, return the preorder traversal of its nodes' values.

Example:

Input:

[1,null,2,3]

1
\
2
/
3

Output:

[1,2,3]

Follow up: Recursive solution is trivial, could you do it iteratively?

一般我們提到樹的遍歷，最常見的有先序遍歷，中序遍歷，后序遍歷和層序遍歷，它們用遞歸實現(xiàn)起來都非常的簡單。而題目的要求是不能使用遞歸求解，于是只能考慮到用非遞歸的方法，這就要用到stack來輔助運算。由于先序遍歷的順序是"根-左-右", 算法為：

1. 把根節(jié)點 push 到棧中

2. 循環(huán)檢測棧是否為空，若不空，則取出棧頂元素，保存其值，然后看其右子節(jié)點是否存在，若存在則 push 到棧中。再看其左子節(jié)點，若存在，則 push 到棧中。

參見代碼如下：

解法一：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if (!root) return {};
        vector<int> res;
        stack<TreeNode*> s{{root}};
        while (!s.empty()) {
            TreeNode *t = s.top(); s.pop();
            res.push_back(t->val);
            if (t->right) s.push(t->right);
            if (t->left) s.push(t->left);
        }
        return res;
    }
};

下面這種寫法使用了一個輔助結(jié)點p，這種寫法其實可以看作是一個模版，對應(yīng)的還有中序和后序的模版寫法，形式很統(tǒng)一，方便于記憶。輔助結(jié)點p初始化為根結(jié)點，while 循環(huán)的條件是棧不為空或者輔助結(jié)點p不為空，在循環(huán)中首先判斷如果輔助結(jié)點p存在，那么先將p加入棧中，然后將p的結(jié)點值加入結(jié)果 res 中，此時p指向其左子結(jié)點。否則如果p不存在的話，表明沒有左子結(jié)點，取出棧頂結(jié)點，將p指向棧頂結(jié)點的右子結(jié)點，參見代碼如下：

解法二：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;
        TreeNode *p = root;
        while (!st.empty() || p) {
            if (p) {
                st.push(p);
                res.push_back(p->val);
                p = p->left;
            } else {
                p = st.top(); st.pop();
                p = p->right;
            }
        }
        return res;
    }
};

到此這篇關(guān)于C++實現(xiàn)LeetCode(144.二叉樹的先序遍歷)的文章就介紹到這了,更多相關(guān)C++實現(xiàn)二叉樹的先序遍歷內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: