홈>
https://leetcode.com/problems/find-bottom- 왼쪽 트리 값/
바이너리 트리를 주면 트리의 마지막 행에서 가장 왼쪽에있는 값을 찾으십시오.
예 1 : 입력 :
2
/ \
1 3
출력 : 1 예 2 : 입력 :
1
/ \
2 3
/ / \
4 5 6
/
7
출력 : 7 참고 : 트리 (예 : 지정된 루트 노드)가 NULL이 아니라고 가정 할 수 있습니다.
성능을 검토하십시오. 감사합니다
using System;
using System.Collections.Generic;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace GraphsQuestions
{
/// <summary>
/// https://leetcode.com/problems/find-bottom-left-tree-value/
/// </summary>
[TestClass]
public class FindBottomLeftTreeValue
{
//Input:
// 2
// / \
// 1 3
[TestMethod]
public void SmallTreeTest()
{
TreeNode root = new TreeNode(2);
root.left = new TreeNode(1);
root.right = new TreeNode(3);
Assert.AreEqual(1, FindBottomLeftValue(root));
}
//Input:
// 1
// / \
// 2 3
// / / \
// 4 5 6
// /
// 7
[TestMethod]
public void BigTreeTest()
{
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.left.left = new TreeNode(4);
root.right = new TreeNode(3);
root.right.left = new TreeNode(5);
root.right.right = new TreeNode(6);
root.right.left.left = new TreeNode(7);
Assert.AreEqual(7, FindBottomLeftValue(root));
}
public int FindBottomLeftValue(TreeNode root)
{
if (root == null)
{
throw new NullReferenceException("root is empty");
}
Queue<TreeNode> Q = new Queue<TreeNode>();
Q.Enqueue(root);
int left = root.val;
while (Q.Count > 0)
{
// we always push the left node first then we peek, so the first item is the most left
//for the entire level of the tree
int qSize = Q.Count;
left = Q.Peek().val;
for (int i = 0; i < qSize; i++)
{
var current = Q.Dequeue();
if (current.left != null)
{
Q.Enqueue(current.left);
}
if (current.right != null)
{
Q.Enqueue(current.right);
}
}
}
return left;
}
}
/*
Definition for a binary tree node.*/
public class TreeNode
{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
}
- 답변 # 1
트렌드
- OpenCv의 폴더에서 여러 이미지 읽기 (python)
- 파이썬 셀레늄 모든 "href"속성 가져 오기
- html - 자바 스크립트 - 클릭 후 변경 버튼 텍스트 변경
- git commit - 자식 - 로컬 커밋 된 파일에 대한 변경을 취소하는 방법
- JSP에 대한 클래스를 컴파일 할 수 없습니다
- javascript - 현재 URL에서 특정 div 만 새로 고침/새로 고침
- jquery - JavaScript로 현재 세션 값을 얻으시겠습니까?
- javascript - swiperjs에서 정지, 재생 버튼 추가
- JavaScript 변수를 HTML div에 '출력'하는 방법
- python - 문자열에서 특정 문자 제거
와이즈 비즈
공연은 나에게 잘 보인다. 몇 가지 주요 관찰 사항 :
정답을 계산하기 위해 모든 노드를 방문해야한다는 것이 확실하므로 솔루션은\ $O (n) \ $시간보다 나을 수 없습니다.리>
레벨 순서대로 탐색하려면 가장 밀도가 높은 레벨의 노드 수만큼 추가 공간이 필요합니다.
깊이를 먼저 여행하려면 뿌리에서 잎까지 가장 긴 경로만큼 추가 공간이 필요합니다.
나무의 모양을 미리 알지 못하고 (깊든 넓든), 주어진
정의 된 추가 도우미 데이터 구조가없는 DFS 또는 BFS가 더 나은지 알 수 없습니다. 공간을 과도하게 사용하지 않기 때문에 둘 다 똑같이 좋습니다.TreeNode