검지offer 제2판 - 55.두 갈래 나무의 깊이
면접 문제 55: 두 갈래 나무의 깊이
제목 요구: 두 갈래 나무의 깊이를 구한다.단지 하나의 뿌리 노드를 포함하는 두 갈래 나무의 깊이는 1이다.
문제 풀이 사고방식: 두 갈래 나무 루트의 깊이가 하위 나무 루트보다 높다.왼쪽과 루트.right의 깊이는 최대 1입니다.따라서 상술한 결론을 통해 점차 해답을 구할 수 있다.반복을 사용하지 않으면 층차 반복 (폭 우선 반복) 을 통해 해결할 수 있습니다.
package chapter6;
import structure.TreeNode;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
/**
* Created with IntelliJ IDEA
* Author: ryder
* Date : 2017/8/15
* Time : 22:25
* Description:
**/
public class P271_TreeDepth {
//
public static int treeDepth(TreeNode root){
if(root==null)
return 0;
int left = treeDepth(root.left);
int right = treeDepth(root.right);
return left>right?(left+1):(right+1);
}
// ， /
public static int treeDepth2(TreeNode root){
if(root==null)
return 0;
Queue> queue = new LinkedList<>();
queue.offer(root);
int depth = 0;
while (!queue.isEmpty()){
int size = queue.size();
TreeNode cur = null;
for(int i=0;i root = new TreeNode<>(1);
root.left = new TreeNode<>(2);
root.left.left = new TreeNode<>(4);
root.left.right = new TreeNode<>(5);
root.left.right.left = new TreeNode<>(7);
root.right = new TreeNode<>(3);
root.right.right = new TreeNode<>(6);
System.out.println(treeDepth(root));
System.out.println(treeDepth2(root));
}
}
실행 결과
4
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
