序遍历非递归

代码实现代码实现思路一先序遍历递归数组代码实现思路二先序遍历非递归以思路一为例进行调试

题目描述

输出[1,null,2,null,3,null,4,null,5,null,6]

输入root

1、在进行先序遍历的时候先将结点的信息存储到数组中通过数组中的先后顺序更新每个结点的指向。

2、复杂度分析

时间复杂度O(n)n为二叉树中节点的个数需遍历一遍二叉树O(n)遍历一遍数组更改指针的指向O(n)。

空间复杂度O(n)递归遍历所需空间最多为O(n)一个额外的数组存储二叉树的信息On。

思路二先序遍历非递归

1、如果我们采用非递归的方式当我们遍历到一个结点时我们就可以用一个指针来记录先序遍历中上一个结点的信息通过修改上一个结点的指向来转换成单链表。

3、复杂度分析

时间复杂度O(n)n为二叉树中节点的个数需遍历一遍二叉树O(n)。

空间复杂度O(n)先序遍历的非递归实现需要借助栈实现最坏情况下栈中有n个结点信息。

代码实现

//方法一递归采用递归的前序遍历将遍历的结点存储在数组中然后修改指针的指向

void

{//nums_TreeNode存放先序遍历各节点的顺序vectorTreeNode

*nums_TreeNode;//先序遍历将结点信息存储在nums_TreeNode中preorder(root,nums_TreeNode);//根据nums_TreeNode中结点的顺序更改结点的指向for

(int

i){nums_TreeNode[i-1]-leftnullptr;nums_TreeNode[i-1]-rightnums_TreeNode[i];}

//注意vectorTreeNode

*nums_TreeNode){if(rootnullptr)

return;nums_TreeNode.emplace_back(root);preorder(root-left,nums_TreeNode);preorder(root-right,nums_TreeNode);

}代码实现思路二先序遍历非递归

//方法二非递归先序遍历,pre代表当前遍历结点的前一个结点改变pre左右孩子结点的指向

void

*stk;stk.push(root);//存放展开单链表的末尾TreeNode

*tailnullptr;while

*nodestk.top();stk.pop();//更改结点的指向if(tail!nullptr)

{tail-leftnullptr;tail-rightnode;}//注意右子结点先入栈if(node-right!nullptr)

stk.push(node-right);if(node-left!nullptr)

stk.push(node-left);//更新单链表的尾结点tailnode;}

#includeiostream

*right;TreeNode():val(0),left(nullptr),right(nullptr){}TreeNode(int

val):val(val),left(nullptr),right(nullptr){}TreeNode(int

val,TreeNode

*right):val(val),left(left),right(right){}

TreeNode

TreeNode(nums[0]);queueTreeNode

q;q.push(root);int

(inums.size()){//注意这里不能用root,会改变root的指向TreeNode

*nodeq.front();q.pop();if(inums.size()nums[i]!-1){node-leftnew

TreeNode(nums[i]);q.push(node-left);}i;if(inums.size()nums[i]!-1){node-rightnew

TreeNode(nums[i]);q.push(node-right);}i;}return

root;

inorder_Traversal(root-left);coutroot-val

;inorder_Traversal(root-right);

}class

public://方法一递归采用递归的前序遍历将遍历的结点存储在数组中然后修改指针的指向void

flatten1(TreeNode*

*nums_TreeNode;preorder(root,nums_TreeNode);for

(int

i){nums_TreeNode[i-1]-leftnullptr;nums_TreeNode[i-1]-rightnums_TreeNode[i];}}//注意vectorTreeNode

preorder(TreeNode

*nums_TreeNode){if(rootnullptr)

return;nums_TreeNode.emplace_back(root);preorder(root-left,nums_TreeNode);preorder(root-right,nums_TreeNode);}

};int

nums{1,2,5,3,4,-1,6};//通过数组创建二叉树-1为nullptrTreeNode*

rootcreateTree(nums);//测试二叉树是否创建正确//inorder_Traversal(root);//二叉树展开为链表Solution

s;s.flatten2(root);//输出转换的单链表while

(root!nullptr){coutroot-val-;rootroot-right;}coutnullptr;return

LeetCode