二叉树的循环遍历方法
最近稍微刷了一下
leetcode，想巩固一下编程功底，但是发现工作后的很少用到在学校时用的数据结构，好多都忘了，在这里做下记录。
¶1.二叉树的前序，中序，后序遍历
前序遍历方向是 中 左 右
中序遍历方向是 左 中 右
后序遍历方向是 右 左 中
根据上面的定义，看的出来对于左右节点，顺序是不变的，只是中间节点出现的位置改变。所以，这也是一个防止忘记的技巧。
¶2.代码实现
# 定义节点对象
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
# 准备测试数据
a = TreeNode(1)
a.left = TreeNode(2)
a.left.left = TreeNode(4)
a.left.right = TreeNode(5)
a.right = TreeNode(3)
a.right.left = TreeNode(6)
a.right.right = TreeNode(7)
class Solution:
def inorderTraversal(self,root):
"""
递归实现中序遍历
"""
if not root:
return []
return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)
def inerderTraversalLoop(self,root):
"""
循环实现中序遍历
"""
result = []
stack = []
curr = root
while curr or stack:
if curr:
stack.append(curr)
curr=curr.left
else:
curr = stack.pop()
result.append(curr.val)
curr = curr.right
return result
def predorderTraversal(self, root):
"""
递归实现前序遍历
"""
if not root:
return []
return [root.val] + self.predorderTraversal(root.left) + self.predorderTraversal(root.right)
def predorderTraversalLoop(self,root):
"""
循环实现前序遍历
"""
result = []
stack = []
curr = root
while curr or stack:
if curr:
result.append(curr.val)
stack.append(curr.right)
curr = curr.left
else:
curr = stack.pop()
return result
def postorderTraversal(self,root):
"""
递归实现后续遍历
"""
if not root:
return []
return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.val]
def postorderTraversalLoop(self,root):
"""
循环实现后续遍历
"""
result = []
stack = []
curr = root
while curr or stack:
if curr:
result.append(curr.val)
stack.append(curr.left)
curr = curr.right
else:
curr = stack.pop()
return result[::-1]
if __name__ == "__main__":
s = Solution()
print(s.inorderTraversal(a))
print(s.inerderTraversalLoop(a))
print(s.predorderTraversal(a))
print(s.predorderTraversalLoop(a))
print(s.postorderTraversal(a))
print(s.postorderTraversalLoop(a))
# [4, 2, 5, 1, 6, 3, 7]
# [4, 2, 5, 1, 6, 3, 7]
# [1, 2, 4, 5, 3, 6, 7]
# [1, 2, 4, 5, 3, 6, 7]
# [4, 5, 2, 6, 7, 3, 1]
# [4, 5, 2, 6, 7, 3, 1]
上面就是实现代码。
先说下递归实现，根据第一节的遍历顺序定义，这里很简单就可以写出递归程序，只是返回的时候，更改下中间节点的位置就好。
在说下循环实现，在LeetCode里面，循环都是hard和middle的题，可见，用循环实现起来并不容易。
主要是要在一个函数里面实现遍历到整个树形结构，如果你能想到用栈（stack）来存节点，那么你应该差不多对数据结构运用有一定经验了。
如下的二叉树
1
2 3
4 5
对于中序遍历
每次将当前结点curr的左子结点push到栈中，直到当前结点curr为None。这时，pop出栈顶的第一个元素，设其为当前结点，并输出该结点的val值，且开始遍历该结点的右子树。当stack和curr都为空的时候，结束循环。
对于前序遍历
输出当前结点curr的val，并将右子结点push到栈中，然后将左子结点设为当前结点。入栈和出栈条件（当前结点curr不为None时，每一次循环将当前结点curr入栈；当前结点curr为None时，则出栈一个结点）以及循环结束条件（整个循环在stack和curr皆为None的时候结束）与中序遍历一模一样。
对于后序遍历
后序遍历在leetcode上是hard难度的题，这里有个技巧，后序是左右中，我们按照中右左的方式遍历，然后反向输出就可以了。而且中右左不就是前序遍历左右互相换下吗？
¶总结
二叉树的循环遍历，还是要借助于栈这个非常有用的数据结构，有时我们都明白，比如，栈啊，队列啊，这些结构有什么特性，但是，要真正灵活的使用这些数据结构，还需要多多练习。