By

前言

Github：https://github.com/HealerJean

博客：http://blog.healerjean.com

1、二叉树展开为链表

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

例如，给定二叉树

	1
   / \
  2   5
 / \   \
3   4   6

将其展开为：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

1.1、解题思路

可以发现展开的顺序其实就是二叉树的先序遍历

1、将左子树插入到右子树的地方

2、将原来的右子树接到左子树的最右边节点

3、考虑新的右子树的根节点，一直重复上边的过程，直到新的右子树为 null

    1
   / \
  2   5
 / \   \
3   4   6

//将 1 的左子树插入到右子树的地方
    1
     \
      2         5
     / \         \
    3   4         6        
//将原来的右子树接到左子树的最右边节点
    1
     \
      2          
     / \          
    3   4  
         \
          5
           \
            6
            
 //将 2 的左子树插入到右子树的地方
    1
     \
      2          
       \          
        3       4  
                 \
                  5
                   \
                    6   
        
 //将原来的右子树接到左子树的最右边节点
    1
     \
      2          
       \          
        3      
         \
          4  
           \
            5
             \
              6

1.2、算法

public void flatten(TreeNode root) {
    while (root != null) {
        if (root.left != null) {
            // 找左子树最右边的节点
            TreeNode pre = root.left;
            while (pre.right != null) {
                pre = pre.right;
            }

            //将原来的右子树接到左子树的最右边节点，此时 pre.right = null
            pre.right = root.right;
            // 将左子树插入到右子树的地方
            root.right = root.left;
            //此时讲root的左节点设置为null
            root.left = null;
            // 考虑下一个节点
        }
        root = root.right;
    }
}

1.3、测试

@Test
public void test(){
    flatten(initTreeNode());
}

​

ContactAuthor