【Check 54】2024-04-17 - 114. 二叉树展开为链表

[larscheng]

114. 二叉树展开为链表

[larscheng]

思路

• 先序遍历(递归/迭代)，在原树中组装链表

  代码

  
  
  class Solution1 {
  public void flatten(TreeNode root) {
      if (root==null){
          return;
      }
      List<TreeNode> list = new ArrayList<>();
      //递归前序遍历（也可迭代）
      helper(root,list);
      //转链表
      for (int i = 0; i < list.size()-1; i++) {
          //i==0时开始改变root的子树结构
          TreeNode node = list.get(i);
          node.left = null;
          node.right = list.get(i + 1);;
      }
  }
  
  private void helper1(TreeNode root, List<TreeNode> list) {
      Stack<TreeNode> stack = new Stack<>();
      stack.push(root);
      while (!stack.isEmpty()){
          TreeNode pop = stack.pop();
          list.add(pop);
          //根->入栈：右-左=》根->出栈：左-右
          if (pop.right!=null){
              stack.push(pop.right);
          }
          if (pop.left!=null){
              stack.push(pop.left);
          }
      }
  }
  private void helper(TreeNode root, List<TreeNode> list) {
      if (root==null){
          return;
      }
      list.add(root);
      helper(root.left, list);
      helper(root.right, list);
  }

}

### 复杂度
- 时间复杂度：O(n)
- 空间复杂度：O(n)

[larscheng]

思路

从根节点开始遍历，如果有左子树，则找左子树最右侧节点指向当前节点的右节点，

当前节点左子树置为null，右子树指向原左子树

代码

class Solution {

    public void flatten(TreeNode root) {
        TreeNode curr = root;
        while (curr != null) {
            if (curr.left != null) {
                TreeNode next = curr.left;
                TreeNode predecessor = next;
                while (predecessor.right != null) {
                    predecessor = predecessor.right;
                }
                predecessor.right = curr.right;
                curr.left = null;
                curr.right = next;
            }
            curr = curr.right;
        }
    }
}

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(1)