LeetCode 144—Binary Tree Prorder Traversal（C++Java Python）

タイトル:http://oj.leetcode.com/problems/binary-tree-preorder-traversal/
Gven a binary tree，return the preorder trversal of its nodes'values.
For example：Given binary tree｛1，33751;，2，3｝
   1    \      2    /    3
return[1,2,3]
Note:Recursive solution is trivial，could you do it teratively？
タイトル翻訳：
二叉のツリーを指定して、そのノード値の前の順序を返します。例えば、二叉の木を与えられました。再帰的な解法は簡単です。反復で実現できますか？分析:
        反復を実現するためにstackを使用する。
C++実現1（再帰版）：

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector preorderTraversal(TreeNode *root) {
    	vector result;

    	if(root != NULL)
    	{
    		result.push_back(root->val);

    		vector left = preorderTraversal(root->left);
    		result.insert(result.end(), left.begin(), left.end());

    		vector right = preorderTraversal(root->right);
    		result.insert(result.end(), right.begin(), right.end());
    	}

    	return result;
    }
};

C++実装2(反復):

class Solution {
public:
    vector preorderTraversal(TreeNode *root) {
    	vector result;

    	if(root == NULL)
    	{
    		return result;
    	}

    	std::stack nodeStack;
    	nodeStack.push(root);

    	while(!nodeStack.empty())
    	{
    		TreeNode *node = nodeStack.top();
    		result.push_back(node->val);
    		nodeStack.pop();

    		if(node->right)
    		{
    			nodeStack.push(node->right);
    		}
    		if(node->left)
    		{
    			nodeStack.push(node->left);
    		}
    	}

    	return result;
    }
};

Java実装1（再帰版）：

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList preorderTraversal(TreeNode root) {
		ArrayList result = new ArrayList();

		if (root != null) {
			result.add(root.val);

			result.addAll(preorderTraversal(root.left));

			result.addAll(preorderTraversal(root.right));
		}

		return result;
    }
}

Java実装2（反復版）：

public class Solution {
    public ArrayList preorderTraversal(TreeNode root) {
		ArrayList result = new ArrayList();

		if (root == null) {
			return result;
		}

		Stack nodeStack = new Stack();
		nodeStack.push(root);

		while (!nodeStack.empty()) { 
			TreeNode node = nodeStack.pop();
			result.add(node.val);

			if (node.right != null) {
				nodeStack.push(node.right);
			}

			if (node.left != null) {
				nodeStack.push(node.left);
			}
		}

		return result;
    }
}

Python実現1（再帰版）：

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @return a list of integers
    def preorderTraversal(self, root):
        result = []
        
        if root != None:
            result.append(root.val)
            
            left = self.preorderTraversal(root.left)
            result.extend(left)
            
            right = self.preorderTraversal(root.right)
            result.extend(right)
        
        return result

Python実装2（反復版）：

class Solution:
    # @param root, a tree node
    # @return a list of integers
    def preorderTraversal(self, root):
        result = []
        
        if root == None:
            return result
        
        nodeStack = []
        nodeStack.append(root)
        
        while len(nodeStack) != 0:
            node = nodeStack.pop()
            result.append(node.val)
            
            if node.right != None:
                nodeStack.append(node.right)
            
            if node.left != None:
                nodeStack.append(node.left)
            
        return result

       読んでくれてありがとうございます。参考資料：http://www.geeksforgeeks.org/iterative-preorder-traversal/