Maximum Depth of Binary Tree_DFS
DFS, Stack
Given the root
of a binary tree, return its maximum depth.
A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

์๋ฃ๊ตฌ์กฐ : Stack
์๊ณ ๋ฆฌ์ฆ 1. ํธ๋ฆฌ ๋ ธ๋๋ฅผ ๋ฃจํธ์์๋ถํฐ ํ๋์ฉ ์คํ์ ๋ฃ๋๋ค. (๋ ธ๋๋ฅผ ๋ฃ๋ ์คํ์ ๊น์ด ๊ฐ ๋ฃ๋ ์คํ, ๊น์ด ๊ฐ์ root=1๋ถํฐ ์์ํ๋ค.) 2. pop()ํ๋ฉด์ ์ผ์ชฝ ์์๊ณผ ์ค๋ฅธ์ชฝ ์์์ด ์์ผ๋ฉด pushํ๋ค. 3. ๋ ธ๋ ์คํ์ ๋ ธ๋๋ฅผ ๋ฃ์ ๋๋ง๋ค ๊น์ด๊ฐ์ +1์ฉ ์ฆ๊ฐํ๋ค. 4. ๊น์ด ๊ฐ์ 1->2->3->4.. ์ฆ๊ฐํ๋ฏ๋ก Math.max(value, max) ๋ก ๊น์ด ๊ฐ์ ๋น๊ตํ๋ฉฐ ์ต๋๊ฐ์ ๋ฆฌํดํ๋ค.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {//DFS, Stack
public int maxDepth(TreeNode root) {
if(root == null) return 0;
Stack<TreeNode> stack = new Stack<>();
Stack<Integer> Vstack = new Stack<>();
stack.push(root);
Vstack.push(1);//root has 1 depth itself.
int max = 0;
while(!stack.isEmpty()) {//till stack is empty, push and pop node and depth value to stack.
TreeNode node = stack.pop();
int value = Vstack.pop();
max = Math.max(max,value);
if(node.left != null) {
stack.push(node.left);
Vstack.push(value+1);
}
if(node.right != null) {
stack.push(node.right);
Vstack.push(value+1);
}
}
return max;
}
}
Last updated
Was this helpful?