欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

114.二叉树展开为链表

程序员文章站 2022-07-16 11:30:21
...

114.二叉树展开为链表

思路:
还是二叉树的先序遍历,最开始先进行判断一下根节点的右字数是否为空,如果不为空则压入栈中,在将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();
   }
  }
 }
};

114.二叉树展开为链表

另外加一种绝妙的递归方法:

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;
    }