114. 二叉树展开为链表

给定一个二叉树，原地将它展开为一个单链表。

例如，给定二叉树

   1
  / \
 2   5
/ \   \
3  4   6
将其展开为：

1
\
 2
  \
   3
    \
     4
      \
       5
        \
         6

代码实现

public void flatten(TreeNode root) {
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode parentNode = root;
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            if (node.right != null){
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }

           if (node != root){
               parentNode.right = node;
               parentNode.left = null;
               parentNode = node;
           }
        }
    }

解题思路

前序遍历二叉树

1. 将root入栈
2. 循环执行以下操作直到栈为空
   2.1. 弹出栈顶节点，进行访问
   2.2. 将右子节点入栈
   2.3. 将左子节点入栈
   2.4. 如果栈顶元素不是根节点，
   2.4.1. 将栈顶元素赋值给上一次访问的栈顶节点的右子节点
   2.4.2. 将上一次访问的栈顶节点的左子节点赋值为空