LeetCode解题思路--树

144. Binary Tree Preorder Traversal

因为要求不能用递归：

def preorder(tree):
    if tree:
        print(tree.getRootVal())
        preorder(tree.getLeftChild())
        preorder(tree.getRightChild())

按照前序遍历树的节点的顺序（逐级往下读左边节点，然后逐级网上返回读右边节点），想到用栈。

• 1 随机画出一个一般的树，然后研究节点入栈的顺序和出栈的操作
• 2 按照先读左边的，就一路读下去，读到叶节点后开始出栈，对每一个出栈的节点，判断是否有右节点，若有，就接着读，接着入栈，没有就继续往上返回出栈
• 3 直到栈内为空，停止循环