题目

image.png

思路

  • 按照先序遍历解决即可

代码

  1.     //1.使用栈
  2.     public void flatten(TreeNode root) {
  3.         if (root == null) return;
  4.         Stack<TreeNode> stack = new Stack<>();
  5.         stack.push(root);
  6.         while (!stack.isEmpty()) {
  7.             TreeNode cur = stack.pop();
  8.             if (cur.right != null) stack.push(cur.right);
  9.             if (cur.left != null) stack.push(cur.left);
  10.             cur.right = stack.isEmpty() ? null : stack.peek();
  11.             cur.left = null;
  12.         }
  13.     }
  15.     //2.递归
  16.     TreeNode prev;
  17.     public void flatten(TreeNode root) {
  18.         if (root == null) return;
  19.         TreeNode right = root.right, left = root.left;
  20.         if (prev != null) prev.right = root;
  21.         prev = root;
  22.         root.left = null;
  23.         flatten(left);
  24.         flatten(right);
  25.     }

二叉树展开为链表