代码随想录——二叉树的所有路径（Leetcode257）需要回顾

题目链接

BFS + 队列

维护一个队列，存储节点以及根到该节点的路径。一开始这个队列里只有根节点。在每一步迭代中，我们取出队列中的首节点，如果它是叶子节点，则将它对应的路径加入到答案中。如果它不是叶子节点，则将它的所有孩子节点加入到队列的末尾。当队列为空时广度优先搜索结束，我们即能得到答案。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<String>();
        if(root == null){
            return res;
        }
        // 节点队列
        Deque<TreeNode> nodeQue = new LinkedList<TreeNode>();
        // 路径（节点值）队列
        Deque<String> pathQue = new LinkedList<String>();

        nodeQue.offer(root);
        pathQue.offer(Integer.toString(root.val));

        while(!nodeQue.isEmpty()){
            TreeNode node = nodeQue.poll();
            String path = pathQue.poll();

			// 如果为叶子节点，则将路径（节点值）加入res结果中
            if(node.left == null && node.right == null){
                res.add(path);
            }else{
                if(node.left != null){
                    nodeQue.offer(node.left);
                    // StringBuffer 是Java中用于处理字符串的一个可变类，它允许我们添加、删除或修改字符串的内容。
                    pathQue.offer(new StringBuffer(path).append("->").append(node.left.val).toString());
                }
                if(node.right != null){
                    nodeQue.offer(node.right);
                    pathQue.offer(new StringBuffer(path).append("->").append(node.right.val).toString());
                }
            }
        }
        return res;
    }
}

DFS + 递归

在深度优先搜索遍历二叉树时，我们需要考虑当前的节点以及它的孩子节点。

• 如果当前节点不是叶子节点，则在当前的路径末尾添加该节点，并继续递归遍历该节点的每一个孩子节点。
• 如果当前节点是叶子节点，则在当前路径末尾添加该节点后我们就得到了一条从根节点到叶子节点的路径，将该路径加入到答案。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<String>();
        getPath(root, "", res);
        return res;
    }

    public void getPath(TreeNode root, String path, List<String> res){
        if(root != null){
            StringBuffer pathSB = new StringBuffer(path);
            // 根节点不空则先加入pathSB
            pathSB.append(Integer.toString(root.val));
            // 如果没有左右孩子则将pathSB加入res
            if(root.left == null && root.right == null){
                res.add(pathSB.toString());
            }else{
                // 递归
                pathSB.append("->");
                getPath(root.left, pathSB.toString(),res);
                getPath(root.right, pathSB.toString(),res);
            }
        }
    }
}