[LeetCode] Binary Tree Paths 二叉树路径

不念不忘少年蓝@ 2022-04-14 04:54 184阅读 0赞

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

1
     /   \
    2     3
     \
      5

All root-to-leaf paths are:

["1->2->5", "1->3"]

`图形化表述:`

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70][]

import java.util.List;
    import java.util.ArrayList;
    public class liubobo_7_4 {
    
    /// 257. Binary Tree Paths
    /// https://leetcode.com/problems/binary-tree-paths/description/
    /// 时间复杂度: O(n), n为树中的节点个数
    /// 空间复杂度: O(h), h为树的高度
    
        // Definition for a binary tree node.
        public class TreeNode {
            int val;
            TreeNode left;
            TreeNode right;
            TreeNode(int x) { val = x; }
        }
    
        public List<String> binaryTreePaths(TreeNode root) {
    
            ArrayList<String> res = new ArrayList<String>();
    
            if(root == null)//递归终止条件，防止放入空树
                return res;
    
            if(root.left == null && root.right == null){//递归终止条件，判断有没有到达叶子节点
                res.add(Integer.toString(root.val));
                return res;
            }
    
            List<String> leftPaths = binaryTreePaths(root.left);//返回所有左子树的路径
            for(String s: leftPaths){
                StringBuilder sb = new StringBuilder(Integer.toString(root.val));
                sb.append("->");
                sb.append(s);
                res.add(sb.toString());
            }
    
            List<String> rightPaths = binaryTreePaths(root.right);//返回所有右子树的路径
            for(String s: rightPaths) {
                StringBuilder sb = new StringBuilder(Integer.toString(root.val));
                sb.append("->");
                sb.append(s);
                res.add(sb.toString());
            }
    
            return res;
        }
    
    }

类似题目:

1.path sum II

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 1][]

2.sum root to leaf numbers

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 2][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70]: /images/20220414/7dd16026c2ba4d8fa1fee011a682ac37.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 1]: /images/20220414/00e111da41ef4478872d6d93dca5f51b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mzk0ODkx_size_16_color_FFFFFF_t_70 2]: /images/20220414/056bc9ecdf994d91a9b9304787a0ff94.png