二叉树的所有路径( LeetCode 257 )

一、题目描述

给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 二叉树的所有路径( LeetCode 257 ):https://leetcode-cn.com/problems/binary-tree-paths/submissions/
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {

        // res 存放所有从根节点到叶子节点的路径。
        List<String> res = new ArrayList<String>();

        // 边界情况处理
        if (root == null) {
            return res;
        }

        // 设置一个队列 nodeQueue,用来遍历存储二叉树中的元素
        Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();

        // 设置一个队列 pathQueue,用来记录路径
        Queue<String> pathQueue = new LinkedList<String>();

        // Queue 中 add() 和 offer()都是用来向队列添加一个元素
        // 在容量已满的情况下,add() 方法会抛出 IllegalStateException 异常,offer() 方法只会返回 false 

        // nodeQueue 队列添加二叉树的根节点
        nodeQueue.offer(root);

        // pathQueue 队列添加二叉树的根节点的值
        pathQueue.offer(Integer.toString(root.val));

        // 遍历队列,直到队列为空,说明访问了二叉树中所有的节点
        while (!nodeQueue.isEmpty()) {

            // 从 nodeQueue 中取出一个节点,此时,nodeQueue 已经抛出了这个节点      
            TreeNode node = nodeQueue.poll(); 

            // 从 pathQueue 中取出一个元素,此时,nodeQueue 已经抛出了这个元素   
            String path = pathQueue.poll();

            // 判断当前节点的左子节点和右子节点是否存在
            // 即判定当前节点是否是叶子节点,如果是叶子节点,那么就找到了一条路径
            if (node.left == null && node.right == null) {
                // 把这条路径添加到结果数组中
                res.add(path);
            } else {

                // 判断当前节点的左子节点是否存在,如果存在,顺着这个节点去寻找叶子节点
                if (node.left != null) {

                    // nodeQueue 队列添加这个存在的左子节点
                    nodeQueue.offer(node.left);

                    // 接下来,需要把这个节点加入到 path 这条路径中
                    StringBuilder strB  = new StringBuilder(path);

                    // 添加 ->
                    strB.append("->");

                    // 添加当前节点的值
                    strB.append(node.left.val);

                    // node.left 成功添加到 path 这条路径中,形成了 newPath
                    String newPath = strB.toString();

                    // pathQueue 队列记录这条路径
                    pathQueue.offer(newPath);

                }

                if (node.right != null) {
                    // nodeQueue 队列添加这个存在的左子节点
                    nodeQueue.offer(node.right);

                    // 接下来,需要把这个节点加入到 path 这条路径中
                    StringBuilder strB  = new StringBuilder(path);

                    // 添加 ->
                    strB.append("->");

                    // 添加当前节点的值
                    strB.append(node.right.val);

                    // node.left 成功添加到 path 这条路径中,形成了 newPath
                    String newPath = strB.toString();

                    // pathQueue 队列记录这条路径
                    pathQueue.offer(newPath);
                }
            }
        }

        // 返回 res
        return res;
    }
}

2、C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 二叉树的所有路径( LeetCode 257 ):https://leetcode-cn.com/problems/binary-tree-paths/submissions/
class Solution
{
public:
    vector<string> binaryTreePaths(TreeNode* root)
    {

        // res 存放所有从根节点到叶子节点的路径。
        vector<string> res;

        // 边界情况处理
        if (root == NULL)
        {
            return res;
        }

        // 设置一个队列 nodeQueue,用来遍历存储二叉树中的元素
        queue<TreeNode*> nodeQueue;

        // 设置一个队列 pathQueue,用来记录路径
        queue<string> pathQueue;

        // Queue 中 add() 和 offer()都是用来向队列添加一个元素
        // 在容量已满的情况下,add() 方法会抛出 IllegalStateException 异常,offer() 方法只会返回 false

        // nodeQueue 队列添加二叉树的根节点
        nodeQueue.push(root);

        // pathQueue 队列添加二叉树的根节点的值
        pathQueue.push(to_string(root->val));

        // 遍历队列,直到队列为空,说明访问了二叉树中所有的节点
        while (!nodeQueue.empty())
        {

            // 从 nodeQueue 中取出一个节点,此时,nodeQueue 已经抛出了这个节点
            TreeNode *node = nodeQueue.front();
            nodeQueue.pop();

            // 从 pathQueue 中取出一个元素,此时,nodeQueue 已经抛出了这个元素
            string path = pathQueue.front();
            pathQueue.pop();

            // 判断当前节点的左子节点和右子节点是否存在
            // 即判定当前节点是否是叶子节点,如果是叶子节点,那么就找到了一条路径
            if (node->left == NULL && node->right == NULL)
            {
                // 把这条路径添加到结果数组中
                res.push_back(path);
            }
            else
            {

                // 判断当前节点的左子节点是否存在,如果存在,顺着这个节点去寻找叶子节点
                if (node->left != NULL)
                {

                    // nodeQueue 队列添加这个存在的左子节点
                    nodeQueue.push(node->left);

                    // 接下来,需要把这个节点加入到 path 这条路径中
                    string strB = path;

                    // 添加 ->
                    strB = strB + "->";

                    // 添加当前节点的值
                    strB = strB + to_string(node->left->val);

                    // pathQueue 队列记录这条路径
                    pathQueue.push(strB);
                }

                if (node->right != NULL)
                {
                    // nodeQueue 队列添加这个存在的左子节点
                    nodeQueue.push(node->right);

                    // 接下来,需要把这个节点加入到 path 这条路径中
                    string strB = path;

                    // 添加 ->
                    strB = strB + "->";

                    // 添加当前节点的值
                    strB = strB + to_string(node->right->val);

                    // pathQueue 队列记录这条路径
                    pathQueue.push(strB);
                }
            }
        }

        // 返回 res
        return res;
    }
};

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者:程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 二叉树的所有路径( LeetCode 257 ):https://leetcode-cn.com/problems/binary-tree-paths/submissions/
class Solution:
    def binaryTreePaths(self, root: TreeNode) -> List[str]:

        # res 存放所有从根节点到叶子节点的路径。
        res = list()

        # 边界情况处理
        if not root :
            return res

        # 设置一个队列 nodeQueue,用来遍历存储二叉树中的元素
        nodeQueue = deque()

        # 设置一个队列 pathQueue,用来记录路径
        pathQueue = deque()

        # Queue 中 add() 和 offer()都是用来向队列添加一个元素
        # 在容量已满的情况下,add() 方法会抛出 IllegalStateException 异常,offer() 方法只会返回 false 

        # nodeQueue 队列添加二叉树的根节点
        nodeQueue.append(root)

        # pathQueue 队列添加二叉树的根节点的值
        pathQueue.append(str(root.val))

        # 遍历队列,直到队列为空,说明访问了二叉树中所有的节点
        while nodeQueue : 

            # 从 nodeQueue 中取出一个节点,此时,nodeQueue 已经抛出了这个节点      
            node = nodeQueue.popleft() 

            # 从 pathQueue 中取出一个元素,此时,nodeQueue 已经抛出了这个元素   
            path = pathQueue.popleft()

            # 判断当前节点的左子节点和右子节点是否存在
            # 即判定当前节点是否是叶子节点,如果是叶子节点,那么就找到了一条路径
            if not node.left and not node.right:
                # 把这条路径添加到结果数组中
                res.append(path)
            else :

                # 判断当前节点的左子节点是否存在,如果存在,顺着这个节点去寻找叶子节点
                if node.left :

                    # nodeQueue 队列添加这个存在的左子节点
                    nodeQueue.append(node.left)

                    # 接下来,需要把这个节点加入到 path 这条路径中
                    # node.left 成功添加到 path 这条路径中,形成了 newPath
                    newPath = path + '->' + str(node.left.val)

                    # pathQueue 队列记录这条路径
                    pathQueue.append(newPath)



                if node.right :

                   # nodeQueue 队列添加这个存在的左子节点
                    nodeQueue.append(node.right)

                    # 接下来,需要把这个节点加入到 path 这条路径中
                    # node.right 成功添加到 path 这条路径中,形成了 newPath
                    newPath = path + '->' + str(node.right.val)

                    # pathQueue 队列记录这条路径
                    pathQueue.append(newPath)

        # 返回 res
        return res

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

发表评论

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