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

Posted on by

[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?

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

1. 把根節點 push 到棧中

2. 循環檢測棧是否為空，若不空，則取出棧頂元素，保存其值，然後看其右子節點是否存在，若存在則 push 到棧中。再看其左子節點，若存在，則 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;
    }
};

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

解法二：

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;
    }
};

到此這篇關於C++實現LeetCode(144.二叉樹的先序遍歷)的文章就介紹到這瞭,更多相關C++實現二叉樹的先序遍歷內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：