乐趣区

关于leetcode:leetcode树之二叉树的所有路径

本文次要记录一下 leetcode 树之二叉树的所有门路

题目

给定一个二叉树,返回所有从根节点到叶子节点的门路。阐明: 叶子节点是指没有子节点的节点。示例:

输出:

   1
 /   \
2     3
 \
  5

输入: ["1->2->5", "1->3"]

解释: 所有根节点到叶子节点的门路为: 1->2->5, 1->3

起源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/binary-tree-paths
著作权归领扣网络所有。商业转载请分割官网受权,非商业转载请注明出处。

题解

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) {val = x;}
 * }
 */
class Solution {public List<String> binaryTreePaths(TreeNode root) {List<String> result = new ArrayList<>();

        if(root == null) {return result;}

        solve(root, "", result);

        return result;
    }

     public void solve(TreeNode root, String cur, List<String> result){if(root == null) {return;}

        cur += root.val;

        if(root.left==null && root.right==null) {result.add(cur);
            return;
        } 

        solve(root.left, cur+"->", result);
        solve(root.right, cur+"->", result);
    }
}

小结

这里采纳递归的思维,设计了 solve 办法,办法有个汇合类型的参数用于收集门路,另外还有一个参数用于示意门路的前缀;每次执行 solve 办法都将以后节点的 val 追加在门路前缀,在节点为叶子节点时,将前缀增加到 result 中并返回;若不为叶子节点则将 -> 拼接到门路前缀中,递归其左右子节点。

doc

  • 二叉树的所有门路
退出移动版