[LeetCode問題解]:Binary Tree Preorder Traversal

3691 ワード

LeetCode

前言

【LeetCode問題解】シリーズ転送ゲート: http://www.cnblogs.com/double-win/category/573499.html

1.タイトルの説明
Given a binary tree, return the preorder traversal of its nodes' values.
For example: Given binary tree {1,#,2,3} ,

return [1,2,3] .
Note: Recursive solution is trivial, could you do it iteratively?
2.題意

先に二叉木を遍歴して、再帰の構想は普通で、反復を使うことができますか?

3.考え方
非再帰的な考え方:

    vector<int> preorderTraversal(TreeNode *root) {

        stack<TreeNode* > st;

        vector<int> vi;

        vi.clear();

        if(!root) return vi;

        

        st.push(root);

        while(!st.empty()){

            TreeNode *tmp = st.top();

            vi.push_back(tmp->val);    

            st.pop();

            if(tmp->right) st.push(tmp->right);

            if(tmp->left) st.push(tmp->left);

        }

        return vi;

    }

再帰的な考え方:

class Solution {

private:

    vector<int> vi;

public:

    vector<int> preorderTraversal(TreeNode *root) {

        vi.clear();

        if(!root) return vi;

        preorder(root);return vi;

    }

    void preorder(TreeNode* root){

        if(!root) return;

        vi.push_back(root->val);

        preorder(root->left);

        preorder(root->right);

    }

};

4.関連テーマ
(1)二叉木の中順遍歴:
(2)二叉木の後順遍歴:
(3)ツリーシリーズの記事:

作者:Double_Win出典:http://www.cnblogs.com/double-win/p/3896010.html 声明:本人のレベルが限られているため、文章の表現とコードの面で不適切な点があれば、批判を歓迎します.

RailsアプリケーションのRubyとBundlerのバージョンをアップデートする

インスタンス変数を{}に宣言し、@propertyキーワードを使用するいくつかの理解