首页 > 其他 > 详细

Leetcode 94. Binary Tree Inorder Traversal

时间:2017-01-04 14:01:12      阅读:235      评论:0      收藏:0      [点我收藏+]

Given a binary tree, return the inorder traversal of its nodes‘ values.

For example:
Given binary tree [1,null,2,3],

   1
         2
    /
   3

return [1,3,2].

 

本题如果用recursive的方法非常简单。这里主要考察用iterative的方法求解。例如: [1,3,4,6,7,8,10,13,14]

技术分享

从8开始依次将8,3,1 push入栈。这时root=None,每当root=None时就从stack里pop一个node出来。并将root定义成3的右子树。然后又是用while root将最左边的一条臂全都推入栈中。

 1 class Solution(object):
 2     def inorderTraversal(self, root):
 3         """
 4         :type root: TreeNode
 5         :rtype: List[int]
 6         """
 7         ans = []
 8         stack = []
 9         while stack or root:
10             while root:
11                 stack.append(root)
12                 root = root.left
13             root = stack.pop()
14             ans.append(root.val)
15             root = root.right
16         return ans
17         

 

Leetcode 94. Binary Tree Inorder Traversal

原文:http://www.cnblogs.com/lettuan/p/6248118.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!