DFS 방식으로 푼 것이 맞나요?

정말 감사합니다. Root, Left, Right 방식으로 코딩을해주셔서 이해가 빨리되었습니다. 결국에 root rigth left도 예제를 추가하니 방향만다르지 동일한 dfs방식이더군요.ㅎㅎ node.right.rigth같은 꼬리가 추가적으로 없어서 이해가 잘 안되었었나봅니다.

원래 의문이었던 dfs가 맞냐는 질문에도 bfs방식이 아니라 dfs방식인것도 확실히 이해하였습니다. (  node.right.rigth 같은 예제 추가를 통해서)

제가 잘 이해한 것이 맞겠죠? ㅎㅎ

안녕하세요~고성빈님

주신 질문 잘 봤습니다. 

먼저 bfs/dfs는 NumberOfIsland로 이해하시면 정통으로 이해하신겁니다.

대부분의 문제는 그렇게 푸시면 될것입니다.^^;

이 문제의 경우에는 약간 헷갈릴수 있는데요

먼저, 이 문제는 Depth를 구할려고하는게 목적입니다.

그래서 queue/stack을 이용했는데요

먼저 queue는 BinaryTreeLevelOrder 문제를 이해하신거처럼 하면됩니다.

(한칸씩 이동하면서 queue에 넣고 삭제하면서 count++ 증가시켜서 depth를 찾고요)

여기서부터 stack의 관한 내용인데요

2가지 관점입니다.

1. TreeNode전체를 dfs로 돌린게 아닙니다.

질문주신내용:(DFS방식이라면 1,2,4,6,5,3식으로 탐색을 해야하는 것이 맞지 않나요?)

네 그렇게 1,2,4,6,5,3식이면 Preorder (Root, Left, Right) 순회하게끔 하면됩니다.

left가 스택에 맨위로 오게해야겠죠 아래처럼 코딩하면됩니다.(full source는 맨 아래 첨부합니다.)

2. 이문제는 stack을 이용할때 각 레벨의 관점에서 담은겁니다.

 각 depth에서 stack으로 담은 후  빼고 있습니다.

 한 depth 들어갈때마다 담은거죠, 그래서 queue랑 다른게 없지 않냐고 하실수 있는데요

(stack으로 담았기 때문에 다른다는거죠)

우리가 보통 bfs는 queue에 담아서 하나 씩 찾아들어가는거

dfs는 stack, 재귀로 꼬리에꼬리를 무는 방식으로 찾아들어가는거로 이해하듯이

각 depth를 stack에 담았기때문에 dfs방식이라고 한것입니다. 

3. 추가적인 의문사항 있으면 바로 질문주세요.  감사합니다.

import java.util.*;

class TreeNode {

int val;

TreeNode left, right;

TreeNode(int x) {

this.val = x;

}

}

public class Dfs_stack {

public static void main(String[] args) {

Dfs_stack a = new Dfs_stack();

TreeNode node = new TreeNode(1);

node.left = new TreeNode(2);

node.right = new TreeNode(3);

node.left.left = new TreeNode(4);

node.left.right = new TreeNode(5);

node.left.left.left = new TreeNode(6);

System.out.println("val: " + a.dfs(node));

System.out.println("val: " + a.dfsStack(node));

}

public List<Integer> dfsStack(TreeNode root) {

List<Integer> lists = new ArrayList<>();

if (root == null)

return lists;

Stack<TreeNode> stack = new Stack<>();

stack.push(root);

while (!stack.isEmpty()) {

TreeNode tree = stack.pop();

if (tree.right != null)

stack.push(tree.right);

if (tree.left != null)

stack.push(tree.left);

lists.add(tree.val);

}

return lists;

}

public int dfs(TreeNode root) {

// 1

if (root == null)

return 0;

Stack<TreeNode> stack = new Stack<>();

Stack<Integer> valueStack = new Stack<>();

stack.push(root);

valueStack.push(1);

int max = 0;

while (!stack.isEmpty()) {

TreeNode node = stack.pop();

// System.out.println("node: " + node.val);

int count = valueStack.pop();

max = Math.max(max, count);

if (node.left != null) {

stack.push(node.left);

valueStack.push(1 + count);

}

if (node.right != null) {

stack.push(node.right);

valueStack.push(1 + count);

}

}

return max;

}

}