Leetcode_num8_Binary Tree Preorder Traversal

题目：Given a binary tree, return the preorder traversal of its nodes‘ values.

此题即为二叉树的前序遍历，递归的方法很简单：先节点再左子树再右子树；迭代的方法可以利用栈存储来完成遍历过程。

补充递归与迭代的区别：许多问题是以递归的形式进行解释的，这只是因为它比非递归形式更为清晰。但是，这些问题的迭代往往比递归实现效率更高，代码的可读性可能稍差一些。当一个问题相当复杂，难以用迭代形式实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开销。当你使用递归时候，一定要考虑它所带来的好处与它的代价之间的比较。

上代码咯~

递归的方法 Python

# 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):
        rs=[]
        if root!=None:
            rs.append(root.val)
            rs+=self.preorderTraversal(root.left)+self.preorderTraversal(root.right)
        return rs

迭代的方法 C++

/**
 * 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 rs;
        stack nstack;
        if (root==NULL)
            return rs;
            
        nstack.push(root); 
        rs.push_back(root->val);
        TreeNode *next = root->left;  
  
        while (next != NULL || !nstack.empty())  
        {   
            while (next != NULL)  
            {  
                rs.push_back(next->val);
                nstack.push(next);  
                next = next->left;  
            }  
            next = nstack.top();  
            nstack.pop();  
            next = next->right;  
        }  
    }
};