Binary Tree Paths

2015-8-18 diaba 数据结构

最近，在https://leetcode.com上开始做些算法题，因为平时不咋捉摸算法，只是工作中用到的，才会接触写，工作已经六年了，记得只有一次大概是10年时设计到一个算法题转化为纯数学题，在演算纸上演算，得到结果后，翻译为代码，以后基本上没有接触到多少算法，当然找工作前也大概看了下的。

言归正传，在leetcode上的题做些记录，从简单地开始。


题的描述：


            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"]
    


自己完成的代码： 


package com.leetcode.algrithm.binarytreepath;

import java.util.ArrayList;
import java.util.List;

public class Solution {
	public static void main(String[] args) {
		Solution t = new Solution();
		TreeNode a = t.new TreeNode(1);
		TreeNode b = t.new TreeNode(2);
		TreeNode c = t.new TreeNode(3);
		TreeNode d = t.new TreeNode(4);
		TreeNode e = t.new TreeNode(5);
		a.left = b;
		a.right = c;
		b.right = e;
		b.left = d;
		System.out.println(t.binaryTreePaths(a));
	}
	
	public List<String> binaryTreePaths(TreeNode root) {

		List<String> resultList = new ArrayList<String>();
		
		if (root == null){
			return resultList;
		}
		
		if (root.left==null && root.right==null){
			resultList.add(""+root.val);
		}
		
		if (root.left!=null ){
			resultList.addAll(binaryTreePaths2("\""+root.val,root.left));
		}
		if (root.right!=null){
			resultList.addAll(binaryTreePaths2("\""+root.val,root.right));
		}
		
		
		return resultList;
	
	}
	
	public static List<String> binaryTreePaths2(String prefix,TreeNode root){
		List<String> result = new ArrayList<String>();
		
		if (root.left == null && root.right == null){
			result.add(prefix + "->"+root.val+"\"");
		}
		if (root.left!=null ){
			result.addAll(binaryTreePaths2(prefix+ "->"+root.val,root.left));
		}
		if (root.right!=null){
			result.addAll(binaryTreePaths2(prefix+ "->"+root.val,root.right));
		}
		return result;
	
	}

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

		TreeNode(int x) {
			val = x;
		}
	}
}


    测试结果：

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

            


    测试通过，本算法原来实现时，递归左子树和右子树时时这样 


if (root.left!=null ){
	return "->"+root.val+binaryTreePaths2(root.left));
}
if (root.right!=null ){
	return "->"+root.val+binaryTreePaths2(root.right));
}
           但是这样有个问题，当root具有左子树和右子树时，那么因为左子树进行递归，递归后直接return，右子树就没有被递归执行，所以后来调整为上述正确的程序。


« 韭菜园正式上线 | Redis设计与实现——链表»

评论：

乐谱吧
2016-07-29 16:05
good非常好
回复

发表评论：

Powered by emlog 京ICP备15045175号-1 Copyright © 2022