二叉树的所有路径

weblog 180 0 0

leetcode257题(简单

原链接:https://leetcode-cn.com/problems/binary-tree-paths/

题目描述

给定一个二叉树,返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例:

输入:

   1
 /   \
2     3
 \
  5

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

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

解题思路

递归得方式遍历二叉树(深度优先搜索),如果是叶子节点就输出从根节点到当前叶子节点多经过的所有节点。递归过程可以用一个栈记录当前经过的所有节点。

代码(java)

/**
 * 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) {
        LinkedList<Integer> linkedList=new LinkedList<>();
        dfs(root,linkedList);
        return li;
    }

   private List<String> li=new ArrayList<>();
    public void dfs(TreeNode node, LinkedList<Integer> list){
        if(node.right==null&&node.left==null){
            StringBuilder builder=new StringBuilder();
            boolean b=true;
            for (Integer integer : list) {
                if(b){
                    b=!b;
                    builder.append(integer);
                }else{
                    builder.append("->").append(integer);
                }
            }
            if(list.size()==0){
                builder.append(node.val);
            }else{
                builder.append("->").append(node.val);
            }
            li.add(builder.toString());
        }else{
            if(node.left!=null){
                list.addLast(node.val);
                dfs(node.left,list);
                list.removeLast();
            }
            if(node.right!=null){
                list.addLast(node.val);
                dfs(node.right,list);
                list.removeLast();
            }
        }
    }
}
执行结果
猜你喜欢
official 155 和一个head为第一个节点链表。如果在中,存在一条一直向下,且每个点数值恰好一一对应以head为首链表中每个节点值,那么请你返回True,否则返回False。一直向下意思
official 174 leetcode第110题(简单)原链接https://leetcode-cn.com/problems/balanced-binary-tree/题目描述给定一个,判断它是否是高度平衡
数据结构与算法 6317 题目:判断下方两棵右方是否为左方例1:||/-----------10(10)------\/-------10(10)------\||||/-------5(5
数据结构与算法 4722 试题描述:思:用数组表示完全,用先序遍历方式遍历每一层节点,用一个数组储存每一层和,因为数据规模小于100000以用一个容量为17数组即可。计算完每一层和,再比较层数最小之和最大
数据结构与算法 4115 整理遍历-(递归法)和(非递归法)-笔记先序遍历、中序遍历、后续遍历、层级遍历。1.节点信息:packagetree;publicclassNodeE{ privateEe;//数据域
数据结构与算法 2459 转载:https://www.cnblogs.com/willwu/p/6007555.html1.定义是一种数据结构,它是由n(n=1)个限节点组成一个具层次关系集合。把它叫做“”是
数据结构与算法 3163 在关于多种算法中都用到了旋转来使保持相对平衡,比如avl,红黑等...1.左旋(pivot为旋转中心点)2.来个动图3.代码演示:/** *左旋 *p为旋转中心点
数据结构与算法 1956 删除节点c++先看一个简单图删除节点是分以下几种情况:1.待删节点为叶子节点:此种情况下直接删除叶子节点即可2.待删节点只左子,或只右子,那么将左子或右子根节点替换该节点即可
目录
祝愿神州十三飞行乘组平安归来