LeetCode 114: Flatten Binary Tree to Linked List

题意描述

给定一棵二叉树，将其平整化为就地链表。

测试用例

For example, given the following tree:

    1
   / \
  2   5
 / \   \
3   4   6

The flattened tree should look like:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

解题思路

一、思路一

分治思想，对于每棵二叉树，将根节点的左节点设为右节点，将原来的右节点设为新右节点（原左节点）的右节点

    public void flatten(TreeNode root) {
            if(root == null) return;
            flatten(root.left);
            flatten(root.right);
            if(root.left != null){	//左节点不为空，执行重连接操作
                TreeNode right = root.right;	//保存右节点
                root.right = root.left;	//更新右节点为左节点
                root.left = null;	//左节点置空
                TreeNode last = root;	//遍历新右节点，找到节点最右的右节点
                while(last.right != null){
                    last = last.right;
                }
                last.right = right;	//连接原右节点
            }
        }

二、思路二

使用栈

• 使用临时节点保存当前节点的右节点，找到左节点的最右节点，并将临时节点连接到最右节点
• 当前节点的右节点更新为左节点，左节点置空
• 如果当前节点的右节点不为空，入栈，继续处理

    public void flatten(TreeNode root) {
            if(root == null) return;
            Stack stack = new Stack<>();
            stack.push(root);
            while(!stack.isEmpty()){
                TreeNode node = stack.pop();
                if(node.left != null){
                    TreeNode left = node.left;	//保存右节点
                    while(left.right != null){	//找到最右节点
                        left = left.right;
                    }
                    left.right  = node.right;	
                    node.right = node.left;
                    node.left = null;
                }
                if(node.right != null){
                    stack.push(node.right);
                }
            }
        }