写出网站建设的基本流程,鹤山市城乡住房建设部网站,网站开发的质量标准,浙江省网站备案注销申请表基于 Morris 遍历思想
将左子树插到右子树的位置#xff0c;将原来的右子树插到左子树的最右结点#xff0c;遍历右结点重复以上步骤#xff0c;直至右结点为空。
class Solution {
public:void flatten(TreeNode* root) {if(rootnullptr) return;while(root){if(!root-将原来的右子树插到左子树的最右结点遍历右结点重复以上步骤直至右结点为空。
class Solution {
public:void flatten(TreeNode* root) {if(rootnullptr) return;while(root){if(!root-left) rootroot-right;else{//找到左子树的最右结点TreeNode* noderoot-left;while(node-right){nodenode-right;}node-rightroot-right;root-rightroot-left;root-leftnullptr;//遍历rootroot-right;}}}
};时间复杂度On空间复杂度O1
后序遍历
链表的顺序与先序遍历相同但如果在先序遍历中修改指针指向会丢失原本的右孩子无法完全遍历。那么不妨进行后序遍历此时会先遍历右左孩子然后更改指针指向。
class Solution {
public:TreeNode* prenullptr;void flatten(TreeNode* root) {if(rootnullptr) return;flatten(root-right);//遍历右子树flatten(root-left);//遍历左子树root-rightpre;//更改指向root-leftnullptr;preroot;//更新pre}
};时间复杂度On空间复杂度Ohh为树的高度递归调用栈
