程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Lettcode_257_Binary Tree Paths

Lettcode_257_Binary Tree Paths

編輯:C++入門知識

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);
		}
	}
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved