80. Binary Tree Paths

1512 단어
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"]

분석: 귀속적인 사상으로 이 문제를 만든다.
왼쪽 결점이 비어 있지 않을 때 왼쪽 결점의 집합을 얻어서root 노드의 값을 각각 왼쪽 결점에서 집합의 각 원소 앞에 넣고 오른쪽 결점에 대해서는 같은 조작을 한다.마지막으로 이 두 집합의 병집을 되돌려줍니다.
/**
	 *  。
	 */
	public List<String> binaryTreePaths(TreeNode root) {
		List<String> list = new ArrayList<String>();
		if(root == null){/* , */
			System.out.println("jj");
			return list;
		}if(root.left==null && root.right == null){
			list.add(root.val+"");
			return list;
		}else{
			List<String> leftList = new ArrayList<String>();
			List<String> rightList = new ArrayList<String>();
			if(root.left != null){/* , root */
				leftList = binaryTreePaths(root.left);
				int llen = leftList.size();
				for(int i=0;i<llen;i++){
					leftList.set(i, root.val+"->"+leftList.get(i));
				}
			}
			if(root.right != null){/* , root */
				rightList = binaryTreePaths(root.right);
				int rlen = rightList.size();
				for(int i=0;i<rlen;i++){
					rightList.set(i, root.val+"->"+rightList.get(i));
				}
			}
			
			list.addAll(leftList);
			list.addAll(rightList);
		}
		
        return list;
    }

좋은 웹페이지 즐겨찾기