二叉树展开为链表( LeetCode 114 )

一、题目描述

给你二叉树的根结点 root ,请你将它展开为一个单链表:

1、展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。

2、展开后的单链表应该与二叉树先序遍历顺序相同。

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 二叉树展开为链表( LeetCode 114 ): https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/
class Solution {

    public void flatten(TreeNode root) {
        backtrack(root);
    }

    // 传入二叉树的节点,把它转换为链表的形式,返回二叉树的尾节点
    private TreeNode backtrack(TreeNode node){

        // 1、如果 node 为空,返回 null
        if(node == null) return null;

        // 2、如果 node 为叶子节点,返回 node
        if(node.left == null && node.right == null) return node;

        // 下面开始设置几个指针

        // 3、left 为当前节点 node 的左子树
        TreeNode left = node.left;

        // 4、right 为当前节点 node 的右子树
        TreeNode right = node.right;

        // 5、leftTail 指向当前节点左子树 left 转换为链表之后的尾节点,一开始默认为 null
        TreeNode leftTail = null;

        // 6、rightTail 指向当前节点右子树 right 转换为链表之后的尾节点,一开始默认为 null
        TreeNode rightTail = null;

        // 7、tail 指向以当前节点 node 为根节点转换为链表之后的尾节点,一开始默认为 null
        TreeNode tail = null;

        // 8、先将 node 的左子树指针置空
        // 将 node 的左子树转换为链表之后,node 的右指针指向那个链表
        node.left = null;

        // 9、如果当前节点存在左子树的时候,那么把左子树转换为链表的形式
        if(left != null){

            // 通过 backtrack 函数递归的把当前节点的左子树转换为链表
            // backtrack 函数指向完之后,left 已经是链表
            // 根据第 5 点的代码,leftTail 指向左子树最后一个节点
            leftTail = backtrack(left);

            // 此时,node 的左子树 left 已经是链表的形式
            // 那么将当前节点 node 的 right 指针指向 left,完成了当前节点和左子树链表的拼接
            node.right = left;

            // 根据第 7 ,tail 指向左子树最后一个节点
            tail = leftTail;
        }


        // 10、如果当前节点存在右子树的时候,那么把左子树转换为链表的形式
        if(right != null){

            // 通过 backtrack 函数递归的把当前节点的右子树转换为链表
            // backtrack 函数指向完之后,right 已经是链表
            // 根据第 6 点的代码,rightTail 指向右子树最后一个节点
            rightTail = backtrack(right);

            // 此时,node 的右子树 right 已经是链表的形式
            // 如果当前节点 node 不存在左子树,那么 node.left = null
            // 由于 node 的右指针就是 right,所以不需要执行其它操作
            // 但如果存在左子树,就需要把 left 链表和 right 链表串联起来
            // 也就是把 left 链表的尾节点和 right 的头节点拼接起来
            if(left != null){
                // 将 leftTail 和 right 转换成的链表链接起来
                leftTail.right = right;
            }

            // 如果存在右子树,那么根据第 7 点的代码,tail 指向右子树最后一个节点
            tail = rightTail;
        }

        // 返回链表的尾节点位置继续去拼接其它的递归链表
        return tail;

    }
}

2、C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 二叉树展开为链表( LeetCode 114 ): https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/
class Solution {
public:
    void flatten(TreeNode* root) {
        backtrack(root);
    }

    // 传入二叉树的节点,把它转换为链表的形式,返回二叉树的尾节点
    TreeNode* backtrack(TreeNode* node){

        // 1、如果 node 为空,返回 NULL
        if(node == NULL) return NULL;

        // 2、如果 node 为叶子节点,返回 node
        if(node->left == NULL && node->right == NULL) return node;

        // 下面开始设置几个指针

        // 3、left 为当前节点 node 的左子树
        TreeNode* left = node->left;

        // 4、right 为当前节点 node 的右子树
        TreeNode* right = node->right;

        // 5、leftTail 指向当前节点左子树 left 转换为链表之后的尾节点,一开始默认为 NULL
        TreeNode* leftTail = NULL;

        // 6、rightTail 指向当前节点右子树 right 转换为链表之后的尾节点,一开始默认为 NULL
        TreeNode* rightTail = NULL;

        // 7、tail 指向以当前节点 node 为根节点转换为链表之后的尾节点,一开始默认为 NULL
        TreeNode* tail = NULL;

        // 8、先将 node 的左子树指针置空
        // 将 node 的左子树转换为链表之后,node 的右指针指向那个链表
        node->left = NULL;

        // 9、如果当前节点存在左子树的时候,那么把左子树转换为链表的形式
        if(left != NULL){

            // 通过 backtrack 函数递归的把当前节点的左子树转换为链表
            // backtrack 函数指向完之后,left 已经是链表
            // 根据第 5 点的代码,leftTail 指向左子树最后一个节点
            leftTail = backtrack(left);

            // 此时,node 的左子树 left 已经是链表的形式
            // 那么将当前节点 node 的 right 指针指向 left,完成了当前节点和左子树链表的拼接
            node->right = left;

            // 根据第 7 ,tail 指向左子树最后一个节点
            tail = leftTail;
        }


        // 10、如果当前节点存在右子树的时候,那么把左子树转换为链表的形式
        if(right != NULL){

            // 通过 backtrack 函数递归的把当前节点的右子树转换为链表
            // backtrack 函数指向完之后,right 已经是链表
            // 根据第 6 点的代码,rightTail 指向右子树最后一个节点
            rightTail = backtrack(right);

            // 此时,node 的右子树 right 已经是链表的形式
            // 如果当前节点 node 不存在左子树,那么 node->left = NULL
            // 由于 node 的右指针就是 right,所以不需要执行其它操作
            // 但如果存在左子树,就需要把 left 链表和 right 链表串联起来
            // 也就是把 left 链表的尾节点和 right 的头节点拼接起来
            if(left != NULL){
                // 将 leftTail 和 right 转换成的链表链接起来
                leftTail->right = right;
            }

            // 如果存在右子树,那么根据第 7 点的代码,tail 指向右子树最后一个节点
            tail = rightTail;
        }

        // 返回链表的尾节点位置继续去拼接其它的递归链表
        return tail;

    }
};

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者:程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 二叉树展开为链表( LeetCode 114 ): https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/
class Solution:
    def flatten(self, root: TreeNode) -> None: 
        self.backtrack(root) 

    # 传入二叉树的节点,把它转换为链表的形式,返回二叉树的尾节点
    def backtrack(self, node: TreeNode) -> TreeNode : 

        # 1、如果 node 为空,返回 None
        if not node :
           return None 

        # 2、如果 node 为叶子节点,返回 node
        if not node.left and not node.right :
           return node 

        # 下面开始设置几个指针

        # 3、left 为当前节点 node 的左子树
        left = node.left 

        # 4、right 为当前节点 node 的右子树
        right = node.right 

        # 5、leftTail 指向当前节点左子树 left 转换为链表之后的尾节点,一开始默认为 None
        leftTail = None 

        # 6、rightTail 指向当前节点右子树 right 转换为链表之后的尾节点,一开始默认为 None
        rightTail = None 

        # 7、tail 指向以当前节点 node 为根节点转换为链表之后的尾节点,一开始默认为 None
        tail = None 

        # 8、先将 node 的左子树指针置空
        # 将 node 的左子树转换为链表之后,node 的右指针指向那个链表
        node.left = None 

        # 9、如果当前节点存在左子树的时候,那么把左子树转换为链表的形式
        if left : 

            # 通过 backtrack 函数递归的把当前节点的左子树转换为链表
            # backtrack 函数指向完之后,left 已经是链表
            # 根据第 5 点的代码,leftTail 指向左子树最后一个节点
            leftTail =  self.backtrack(left) 

            # 此时,node 的左子树 left 已经是链表的形式
            # 那么将当前节点 node 的 right 指针指向 left,完成了当前节点和左子树链表的拼接
            node.right = left 

            # 根据第 7 ,tail 指向左子树最后一个节点
            tail = leftTail 



        # 10、如果当前节点存在右子树的时候,那么把左子树转换为链表的形式
        if right : 

            # 通过 backtrack 函数递归的把当前节点的右子树转换为链表
            # backtrack 函数指向完之后,right 已经是链表
            # 根据第 6 点的代码,rightTail 指向右子树最后一个节点
            rightTail =  self.backtrack(right) 

            # 此时,node 的右子树 right 已经是链表的形式
            # 如果当前节点 node 不存在左子树,那么 node.left = None
            # 由于 node 的右指针就是 right,所以不需要执行其它操作
            # 但如果存在左子树,就需要把 left 链表和 right 链表串联起来
            # 也就是把 left 链表的尾节点和 right 的头节点拼接起来
            if left : 
                # 将 leftTail 和 right 转换成的链表链接起来
                leftTail.right = right 


            # 如果存在右子树,那么根据第 7 点的代码,tail 指向右子树最后一个节点
            tail = rightTail 


        # 返回链表的尾节点位置继续去拼接其它的递归链表
        return tail 

四、动画理解(没有声音)

发表评论

邮箱地址不会被公开。 必填项已用*标注