LeetCode의 두 갈래 트리 차원 역순 출력(단순 두 갈래 트리)

문제 설명:
두 갈래 나무를 정해서 노드 값이 밑에서 위로 올라가는 차원을 되돌려줍니다.(즉, 잎 노드가 있는 층에서 뿌리 노드가 있는 층으로 한 층씩 왼쪽에서 오른쪽으로 옮겨간다)
예를 들어 두 갈래 나무를 지정합니다[3,9,20,null,null,15,7] ,
    3
   / \
  9  20
    /  \
   15   7

아래에서 위로 올라가는 단계를 다음과 같이 되돌려줍니다.
[
  [15,7],
  [9,20],
  [3]
]

간단한 문제라고 말하지만, 나는 그다지 간단하다고 생각하지 않고, 그래도 약간의 정신을 잃었다.코드를 보자마자 알겠지, 아니면 대신에게서 얻은 생각인지.
이것은 옳고 그름의 실현이고, 그름의 실현은 스스로 생각해 내지 못했다
 public List> levelOrderBottom(TreeNode root) {
        LinkedList> res = new LinkedList<>();
        Queue q = new LinkedList<>();
        if(root == null){
            return res;
        }
        q.add(root);
        while(!q.isEmpty()){
            int size = q.size();
            List list = new ArrayList<>();

            for (int i = 0; i < size ; i++) {
                TreeNode t = q.poll();
                list.add(t.val);
                if(t.left!=null){
                    q.add(t.left);
                }
                if(t.right!=null){
                    q.add(t.right);
                }
            }
             res.addFirst(list);
        }
        return res;
    }

또 대신의 귀속 실현을 참고하라. 대신은 정말 대단하다. 무엇이든지 너에게 귀속을 시켜주겠다. 하하, 요리는 내 요리야.
public List> levelOrderBottom(TreeNode root) {
  	List> result = new ArrayList<>();
		HashMap> map = new HashMap<>();//level VS nodes in this level
		fillMap(map,root,1);
		//int i = map.size();
		for( int i = map.size();i>0;i--) {
			result.add(map.get(i));
		}
		return result;
    }
    private void fillMap(HashMap> map, TreeNode node, int level) {
		if(node == null ) {
			return;
		}
		if(map.containsKey(level)) {
			map.get(level).add(node.val);
		}else {
			List list= new ArrayList<>(); 
			list.add(node.val);
			map.put(level, list);
		}
		fillMap(map, node.left, level+1);
		fillMap(map, node.right, level+1);
	 }

좋은 웹페이지 즐겨찾기