老规矩,基本概念不讲了,多看看网上的各种大牛文章。在这里说说自己观点,再拿几道例题演示下。想研究更高级的话,找个红黑树或者其他之类的去玩玩,保你酸爽!
个人感觉还是动态规划更难搞定些!上次的动态规划
二叉树的遍历基本上分为递归和迭代(非递归),在遍历的方式上又有些区别,首当其冲的是前中后序遍历(preorder traversal, inorder traversal, postorder travesal)然后还有深度优先遍历(Deep-First Search)和广度优先遍历(Breadth-First Search)
分析问题先从两个方面入手吧,其一是遍历方式(前序、中序、后序、深度优先、广度优先),其二是选择递归或者非递归
- 例1 LeetCode 145. Binary Tree Postorder Traversal
这道题中,我们先用recursive实现吧,然后再说用iterative
选择了递归后,再看一下用什么遍历方式。根据题意,直接选择后序遍历。
python代码如下:
"""
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
"""
class Solution(object):
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
#recursive
res = []
if not root: return res
def post( node, res ):
if node.left: post( node.left, res )
if node.right: post( node.right, res )
res.append( node.val )
post( root, res )
return res
现在换成iterative方式。用这种方式基本上都是从顶到底进行遍历,所以需要记录当前node和child node,并且这些node需要按照某些顺序进出,这里采用stack可以满足要求
再看遍历方式,分析题目中的例子得知,针对该题后序遍历就是广度优先遍历结果的反向排序
python代码如下:
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
#iterative
res = []
if not root: return res
sta = [root]
while len(sta) > 0:
node = sta[-1]
sta.pop()
if node.left: sta.append( node.left )
if node.right: sta.append( node.right )
res.append( node.val )
return res[-1::-1]
有优化空间的,欢迎各位优化,欢迎交流!
这里采用非递归吧。分析题意后,发现利用广度优先遍历(BFS)最好,我们用一个stack保存当前level的所有节点(按照广度优先顺序,每个level都是从左至右),所以每层level中,stack中最后一个节点就是我们要找的
python代码如下:
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def rightSideView(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
sta = []
res = []
if not root: return res
sta.append( root )
while len(sta) > 0:
res.append( sta[-1].val )
sta = [ kid for node in sta for kid in (node.left, node.right) if kid ]
return res
以上代码有优化空间的,欢迎各位优化,欢迎交流!
还会接着更几题!
网友评论