描述

257. 二叉树的所有路径 - 力扣（Leetcode）

分析

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
import java.util.ArrayList;
import java.util.Stack;
import java.util.List;


//257. 二叉树的所有路径
public class BinaryTreePaths257 {
	public static void main(String[] args){
		TreeNode root = MyUtils.buildTree(new Integer[]{1,2,3,null,5});
		for (String s : new Solution().binaryTreePaths(root)) {
			System.out.println(s);
		}
	}
}

class Solution {
    public List<String> binaryTreePaths1(TreeNode root) {
    	List<String> res = new ArrayList<>();
    	if (root == null) {
    		return res;
    	}
    	List<Integer> paths = new ArrayList<>();
    	traversal(root, paths, res);
    	return res;
    }
    void traversal(TreeNode node,List<Integer> paths, List<String> res){
    	//处理中
    	paths.add(node.val);
    	//退出条件
    	if (node.left == null && node.right == null) {
    		StringBuilder temp = new StringBuilder();
    		for (int i = 0; i < paths.size() - 1; i++) {
    			temp.append(paths.get(i) + "->");
    		}
    		temp.append(paths.get(paths.size() - 1));
    		res.add(temp.toString());
    		return;
    	}
    	//左边
    	if(node.left != null){
    		//递归
    		traversal(node.left,paths,res);
    		//回溯
    		paths.remove(paths.size() - 1);
    	}
    	//右边
    	if(node.right != null){
    		//递归
    		traversal(node.right,paths,res);
    		//回溯
    		paths.remove(paths.size() - 1);
    	}
    }

     public List<String> binaryTreePaths(TreeNode root) {
    	List<String> res = new ArrayList<>();
    	if (root == null) {
    		return res;
    	}
    	Stack<Object> stack = new Stack<>();
    	stack.push(root);
    	stack.push(root.val + "");
    	String path;
    	TreeNode tempNode;
    	while(!stack.isEmpty()){
    		path = (String)stack.pop();
    		tempNode = (TreeNode)stack.pop();
    		//找到叶子节点
    		if (tempNode.left == null && tempNode.right == null) {
    			res.add(path);
    		}
    		if (tempNode.left != null) {
    			stack.push(tempNode.left);
    			stack.push(path + "->" + tempNode.left.val);
    		}
    		if (tempNode.right != null) {
    			stack.push(tempNode.right);
    			stack.push(path + "->" + tempNode.right.val);
    		}
    	}
    	return res;
    }
}



class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	public TreeNode(){};
	public TreeNode(int val){this.val = val;}
	public TreeNode(int val, TreeNode left, TreeNode right){
		this.val = val;
		this.left = left;
		this.right = right;
	}
}


class MyUtils {
	/**
	 *二叉树的构建
	 * int[] -> 二叉树
	 */
	 public static TreeNode buildTree(Integer[] arr) {
        return buildTreeHelper(arr, 0);
    }

    public static TreeNode buildTreeHelper(Integer[] arr, Integer index) {
        if (index >= arr.length || arr[index] == null) {
            return null;
        }

        TreeNode node = new TreeNode(arr[index]);

        node.left = buildTreeHelper(arr, 2 * index + 1);
        node.right = buildTreeHelper(arr, 2 * index + 2);

        return node;
    }
}

总结