主要是迭代实现
深度优先使用栈，广度优先使用队列
使用栈，主要是为了暂存之后会用的父节点。每个节点都可以作为父节点。
前序遍历比较简单，中序遍历和后序遍历思路比较接近。
对于前序遍历，父节点首先(直接)访问，而且用过就不会再用了。之后先存右，再存左。然后取左，重复。父节点不需要被回溯
对于中序遍历，父节点在访问过左子树后访问，即访问前要先保证左子树为空或者访问过，所以是先保存，后访问，访问完再保存右子树，然后访问右子树。
对于后序遍历，父节点最后访问，保存完父节点，先保存左子树，访问，之后通过父节点保存右子树，访问，之后再访问父节点。也就是父节点会多路过一次。父节点访问前要判断左右子树已经都访问过了。因为回溯到父节点，左子树一定已经访问过，因此就是要判断右子树访问过没有。右子树访问之后，紧接就是父节点的访问，因此可以用last变量记录上一次访问的地方。
判断回溯的标准，就是当前遍历节点为nil，此时只能从栈中取一个出来。取出来的也就是父节点，根据中序或者后序，决定是否转到右节点。对于后序，访问完父节点就是访问上一个父节点，因此当前节点要置nil；对于中序，访问完父节点，访问右子树，因此转到右子树，右子树为空，则再转。
144. Binary Tree Preorder Traversal
Given a binary tree, return the preorder traversal of its nodes' values.
迭代实现，利用后进先出的栈实现，
首先利用数组实现一个简单的栈，（也可以直接用数组写在代码当中，分开写虽然需要建立的新的数据结构，但是思路会更清晰，何况其他语言大部分都是有现成的栈结构可用。。）
根节点不放栈中，当前节点为根节点
当前节点不为空，则读取当前节点，栈保存当前节点的两个子节点，
栈不为空，则从栈中重新取一个节点，迭代
94. Binary Tree Inorder Traversal
Given a binary tree, return the inorder traversal of its nodes' values.
145. Binary Tree Postorder Traversal
Given a binary tree, return the postorder traversal of its nodes' values.
树的后序遍历
注意，调用结构体的成员，要记得加先绑定到实例上，不要直接使用变量名。
注意，把for循环误写成if，好久才发现！！！（前序是if，但是后两者是for）
后序遍历的关键就是或者转右，或者访问当前，访问当前，如果当前节点不是空，则要将当前节点置空
网友评论