114.二叉树展开为链表
程序员文章站
2022-07-16 11:30:21
...
思路:
还是二叉树的先序遍历,最开始先进行判断一下根节点的右字数是否为空,如果不为空则压入栈中,在将p指向根节点的左子树,然后再进入循环。这样做的目的是便于控制循环的条件,而且最后要求的目标树的根节点就是一开始树的根节点。循环中的操作就是二叉树的先序遍历的非递归操作了。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void flatten(TreeNode* root) {
stack<TreeNode* > s;
TreeNode* p = root;
if (!root) return;
if (root->right) s.push(root->right);
p = p->left;
while (p || !s.empty())
{
if (p)
{
if (p->right) s.push(p->right);
root->right = p;
p = p->left;
root->left = NULL;
root = root->right;
}
else if (!s.empty())
{
p = s.top();
s.pop();
}
}
}
};
另外加一种绝妙的递归方法:
TreeNode* last = nullptr;
void flatten(TreeNode* root) {
if (root == nullptr) return;
flatten(root->right);
flatten(root->left);
root->right = last;
root->left = nullptr;
last = root;
}
上一篇: 动态规划解决最长公共序列
下一篇: 7-1 最大子列和问题