leetcode || 114、Flatten Binary Tree to Linked List

problem:
Given a binary tree, flatten it to a linked list in-place.
For example, Given
         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:
   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

click to show hints.
Hide Tags
 
Tree Depth-first Search
제목: 두 갈래 나무를 평평하게 하여 왼쪽 나무를 비우다
thinking:
(1) 이 문제는 비교적 재미있다. 제목은linkedlist를 언급했는데 정말list로 전환하는 것이 아니라 두 갈래 나무의 왼쪽 나무를 공중에 띄우고 모두 오른쪽 나무에 걸었다.
(2) 나의 해법: 관찰을 통해 알 수 있듯이 노드 노드의 왼쪽 아이가 비어 있지 않으면 오른쪽으로 옮겨야 하고 왼쪽 아이는 비어야 하며 오른쪽 아이는 왼쪽 아이가 바뀌어야 한다.
Stack를 사용하여 오른쪽 아이를 저장합니다.창고에 귀속되어 창고를 나와 전환을 완성하다.
(3) 창고의 역할은 아이가 접속하는 순서와 시기를 제어하는 것이다.이곳은 더욱 간소화할 수 있다.
code:
Stack법의 적용:
class Solution {
  private:
      stack<TreeNode *> _stack;
  public:
      void flatten(TreeNode *root) {
          if(root==NULL)
              return;
          TreeNode *node=root;
              while(node->left!=NULL) // , , 
              {
                  if(node->right!=NULL)
                      _stack.push(node->right);
                  node->right=node->left;
                  node->left=NULL;
                  node=node->right;
              }
              while(node->left==NULL && node->right!=NULL)// , , 
              {
                  node=node->right;
              }
              if(node->left!=NULL) // , , , 
                 flatten(node);
              if(!_stack.empty()) // , 
              {
                  TreeNode *tmp=_stack.top();
                  _stack.pop();
                  node->right=tmp;
                  flatten(tmp);
              }          
      }
  
  };

단순화:
class Solution {
public:
 
    TreeNode *pre=NULL;
 
    void flatten(TreeNode *root) {
        if(root==NULL)
            return;
        TreeNode *lastright=root->right;// 
        if(pre)
        {
            pre->left=NULL;
            pre->right=root;
        }
        pre=root;
        flatten(root->left);
        flatten(lastright);
    }
};

좋은 웹페이지 즐겨찾기