114. 二叉树展开为链表

开篇闲话：
之前一直准备春招，感觉刷题后，补博客很耗时间，所以中断博客记录刷题历程。2019.4.11拿到拼多多offer已经过去一个星期了，也是躺着放松了一星期，今天开始继续刷leetcode，希望自己可以保持对算法的敏感度，同时继续开启刷题写博客的模式，菜鸡加油。
因为太菜，又过了一星期没动过脑子，所以挑了两题深度遍历的二叉树相关题目练手，思路比较明显直接，两题都是直接靠自己思路ac的！

1. 题目
题目链接
114. 二叉树展开为链表

2. 题目分析
将二叉树展开为链表，看完事例才明白，所谓的链表原来还是二叉树，只是这颗新的二叉树上的所有节点只有右子树，所有左子树为空的假链表。

3. 解题思路
对于二叉树的操作的思路，一般就是使用递归，语义简单明了，将整颗二叉树抽象成一个节点root+一个左节点（左子树）+一个右节点（右子树），然后然后理清操作节点的思路，将二叉树展开为链表，即先将左节点当成新的右节点（new right node）挂到root的右指针上，然后把原来的右节点（old right node）挂到新的右节点（原来的左节点left）的右指针上，这就是转换的过程实现步骤。所以递归就很容易实现了，看如下源码。

4. 代码实现（java）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        if(root == null){
            return ;
        }
        root = treeTranslateIntoLinkedList(root);
        
    }
    public TreeNode treeTranslateIntoLinkedList(TreeNode root) {
        if(root == null){
            return null;
        }
        
        TreeNode right = root.right;
        if(root.left != null){
            root.right = treeTranslateIntoLinkedList(root.left);
  
            TreeNode p = root.right;
            //找到新的右子树的最后那个右节点（叶子节点），然后将原来的右子树挂到这个右节点
            while(p.right != null){
                p = p.right;
            }
            p.right = treeTranslateIntoLinkedList(right);
        }else{
            root.right = treeTranslateIntoLinkedList(root.right);
        }
        root.left = null;//记得要把左子树设置为空
        return root;
    }
}

114. 二叉树展开为链表

114. 二叉树展开为链表

相关推荐