【LeetCode】Binary Tree Preorder Traversal

Binary Tree Preorder Traversal

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?

Solution:

递归解法很简单：

 # Definition for a binary tree node.

 # class TreeNode:

 #     def __init__(self, x):

 #         self.val = x

 #         self.left = None

 #         self.right = None

 class Solution:

     # @param {TreeNode} root

     # @return {integer[]}

     def preorderTraversal(self, root):

         if root == None:

             return []

         else:

             return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)

迭代版本也是常规的将递归改成迭代的版本：

用一个栈来模拟递归的过程，注意栈 FILO 的特点。所以，对于当前根，要把右子树先加入栈，然后再把左子树加入栈。

前序遍历的顺序是：根 - 左子树 - 右子树。

代码如下：

 # Definition for a binary tree node.

 # class TreeNode:

 #     def __init__(self, x):

 #         self.val = x

 #         self.left = None

 #         self.right = None

 class Solution:

     # @param {TreeNode} root

     # @return {integer[]}

     def preorderTraversal(self, root):

         stack = []

         path = []

         if root != None:

             stack.append(root)

         while stack != []:

             e = stack.pop()

             path.append(e.val)

             if e.right != None:

                 stack.append(e.right)

             if e.left != None:

                 stack.append(e.left)

         return path

巴特西

【LeetCode】Binary Tree Preorder Traversal

Binary Tree Preorder Traversal

最新文章

热门文章