首页 > 代码库 > [leetcode]Binary Tree Preorder Traversal @ Python
[leetcode]Binary Tree Preorder Traversal @ Python
原题地址:http://oj.leetcode.com/problems/binary-tree-preorder-traversal/
题意:这题用递归比较简单。应该考察的是使用非递归实现二叉树的先序遍历。先序遍历的遍历顺序是:根,左子树,右子树。
解题思路:如果树为下图:
1
/ \
2 3
/ \ / \
4 5 6 7
使用一个栈。步骤为:
一,先遍历节点1,并入栈,如果有左孩子,继续遍历并入栈,一直到栈为{1,2,4}。
二,开始弹栈,当栈顶元素为2时,弹出2,并检测2存在右孩子5,于是遍历5并入栈,此时栈为{1,5}。
三,弹出5,5没有左右孩子,继续弹栈,将1弹出后,栈为{}。
四,由于1存在右孩子,则继续按照以上步骤入栈出栈。{3, 6}->{7}->{},结束。
栈的状态变化:{1}->{1,2}->{1,2,4}->{1,2}->{1}->{1,5}->{1}->{}->{3}->{3,6}->{3}->{}->{7}->{}。
代码:
# 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 iterative_preorder(self, root, list): stack = [] while root or stack: if root: list.append(root.val) stack.append(root) root = root.left else: root = stack.pop() root = root.right return list def recursive_preorder(self, root, list): if root: list.append(root.val) self.preorder(root.left,list) self.preorder(root.right,list) def preorderTraversal(self,root): list = [] self.iterative_preorder(root,list) return list
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。