Lettcode_257_Binary Tree Paths

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]

思路：

（1）題意為給定一棵樹，找出所有從根到葉子節點的路徑。

（2）該題實為樹的深度優先遍歷。本題是使用遞歸的方法來進行求解的，從根節點開始，若左子樹不為空，則遍歷左子樹，若左子樹的左孩子不為空，則遍歷左孩子，否則遍歷右孩子.....直到遍歷完最後一個葉子節點為止。使用非遞歸算法，則需要設定一個棧來保存左右子樹，也很好實現，這裡不累贅了。

（3）詳情見下方代碼。希望本文對你有所幫助。

package leetcode;

import java.util.ArrayList;
import java.util.List;
import leetcode.utils.TreeNode;

public class Binary_Tree_Paths {

	public static void main(String[] args) {
		TreeNode r = new TreeNode(1);
		TreeNode r1 = new TreeNode(2);
		TreeNode r2 = new TreeNode(3);
		TreeNode r3 = new TreeNode(5);

		r.left = r1;
		r.right = r2;
		r1.right = r3;

		binaryTreePaths(r);
	}

	public static List binaryTreePaths(TreeNode root) {
		List result = new ArrayList();

		if (root != null) {
			getpath(root, String.valueOf(root.val), result);
		}
		return result;
	}

	private static void getpath(TreeNode root, String valueOf,
			List result) {
		if (root.left == null && root.right == null)
			result.add(valueOf);

		if (root.left != null) {
			getpath(root.left, valueOf + -> + root.left.val, result);
		}

		if (root.right != null) {
			getpath(root.right, valueOf + -> + root.right.val, result);
		}
	}
}