力扣114. 二叉树展开为链表

Problem: 114. 二叉树展开为链表

文章目录

• 题目描述
• 思路
• 复杂度
• Code

  题目描述

  

  思路

  将问题进行分解，将一个节点的右指针指向其左子树，再将原始的左子树拼接到当前的右子树上；由于要提前获取一个节点的左、右子树，则需要利用二叉树后序遍历的操作；

  复杂度

  时间复杂度:

  O ( n ) O(n) O(n)；其中 n n n为二叉树节点的个数

  空间复杂度:

  O ( n ) O(n) O(n)

  Code

  class Solution {
      /**
       * Flatten Binary Tree to Linked List
       *
       * @param root The root node of binary tree
       */
      public void flatten(TreeNode root) {
          if (root == null) {
              return;
          }
          flatten(root.left);
          flatten(root.right);
          TreeNode leftNode = root.left;
          TreeNode rightNode = root.right;
          //Treat the left subtree as the right subtree
          root.right = leftNode;
          root.left = null;
          //Connect the original right subtree
          // to the end of the current right subtree
          TreeNode p = root;
          while (p.right != null) {
              p = p.right;
          }
          p.right = rightNode;
      }
  }