先序遍历
思路
遍历顺序为根、左、右
1.如果根节点非空，将根节点加入到栈中。
2.如果栈不空，弹出出栈顶节点，将其值加加入到数组中。
如果该节点的右子树不为空，将右子节点加入栈中。
如果左子节点不为空，将左子节点加入栈中。
3. 重复第二步，直到栈空。
代码实现
中序遍历
思路
遍历顺序为左、根、右
1.如果根节点非空，将根节点加入到栈中。
2.如果栈不空，取栈顶元素（暂时不弹出），
如果左子树已访问过，或者左子树为空，则弹出栈顶节点，将其值加入数组，如有右子树，将右子节点加入栈中。
如果左子树不为空，则将左子节点加入栈中。
3.重复第二步，直到栈空。
代码实现
后序遍历
思路
遍历顺序为左、右、根
1.如果根节点非空，将根节点加入到栈中。
2.如果栈不空，取栈顶元素（暂时不弹出），
如果（左子树已访问过或者左子树为空），且（右子树已访问过或右子树为空），则弹出栈顶节点，将其值加入数组，
如果左子树不为空，切未访问过，则将左子节点加入栈中，并标左子树已访问过。
如果右子树不为空，切未访问过，则将右子节点加入栈中，并标右子树已访问过。
3.重复第二步，直到栈空。
代码实现
网友评论