采用tree traversal (树遍历(前置)二叉树的前置遍历1. tree traversal ) 1.1深度优先搜索)作为优先顺序http://www
深度优先搜索策略可以根据根节点、左孩子树和右孩子树的相对顺序被细分为前序遍历、中序遍历和后序遍历。
1.2宽首搜索-宽首搜索-横向首搜索(breadth-first search，BFS )前序遍历 (preorder traversal) - 中序遍历 (inorder traversal) - 后序遍历 (postorder traversal)
根据各种策略遍历下图中的节点，访问顺序均为1、2、3、4、5。 宽度优先搜索的划分级别为[1]、[ 2，3 ]、[ 4，5 ]。
如果在我们按照高度顺序一层一层的访问整棵树，高层次的节点将会比低层次的节点先被访问到。函数中使用了两个递归调用，则效率低下的问题会更加严重。
2 .二叉树的前序扫描给定某二叉树，返回其前序扫描。
输入： [1，null，2，3 ]1(2/3) : [ 1，2，3 ] int * preorder traversal (struct treenode * root，int * returnsizzernsitizal )
2.1迭代实现-数组模拟栈(stack )操作从根节点开始，每次迭代弹出当前栈顶元素，将其子节点推入栈中，首先推入右边子节点，然后推入左边子节点。 Top - Bottom和Left - Right在最终结果中的输出顺序与上一个导线的顺序一致。
递归实现的效率一般比对应的非递归实现低。:正好访问每个节点一次。 时间复杂度为o(n )。 这里，n是节点的数量，即树的大小。
时间复杂度:根据树的结构，最坏的情况是可以容纳整个树，空间复杂度为o(n )。
设置将根节点推送到堆栈的堆栈。 检测循环堆栈是否为空，如果不为空，则取出堆栈顶部元素并保存其值。 检查堆栈顶部元素右侧的子节点是否存在，如果存在，则将其推送到堆栈中。 显示堆栈顶级元素的左子节点，如果存在，则将其推送到堆栈中。 2 .继续运行，直到堆栈被清空。 //=======================================================================================2020//copyright : copyright (c ) 2019 yongqiang cheng//description : hello world Inc， ansi-style//====================ansi-style/=====================================================* struct TreeNode *right； *； //* * note : thereturnedarraymustbemalloced，assumecallercallsfree (.*.*/int * preorder traversal (struct treeenode ) ) struct TreeNode* pnode=NULL； int*ret=(int* ) malloc ) 256*sizeof ) int )； *returnSize=0； if () null==root) null==returnsize ) {return NULL； (}front=-1； STACK_DATA[ front]=root； while(front=0) {pnode=STACK_DATA[front]； front----； ret[idx]=pnode-val； idx； if (空！=pnode-right (stack _ data [ front ]=pnode-right； (if )空值！=pnode-left ({ stack _ data [ front ]=pnode-left； }}*returnSize=idx； 返回； }
3 .前向遍历-前向遍历首先沿着左侧路径自上而下地访问沿途节点，然后自下而上地遍历这些节点的右子树
空间复杂度
references https://leet code-cn.com /