두 갈래 나무의 각종 알고리즘 면접문제 및 답안 해석
47758 단어 개인 블로그데이터 구조와 알고리즘
전언
아래의 모든 면접문제와 해석 답안은 검증을 거친 것이다.
문서 목록
면접 문제
나무의 정의
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
트리의 결점 수량 계산하기 (귀속)
나무의 결점 수량은 왼쪽 나무에 오른쪽 글자를 더한 수량+1과 같다
public class Solution {
public int sumOfNode(TreeNode root) {
if(root==null){
return 0;
}
int leftSum=sumOfNode(root.left);
int rightSum=sumOfNode(root.right);
return leftSum+rightSum+1;
}
}
트리의 결점 수량 계산하기 (비귀속)
대기열을 사용하여 상층 결점을 꺼내는 동시에 하층 좌우 서브노드를 저장합니다
public class Solution {
public int sumOfNode(TreeNode root) {
if(root==null){
return 0;
}
Queue<TreeNode> queue=new LinkedList<TreeNode>();
queue.offer(root);
int sum=0；
while(!queue.isEmpty()){
TreeNode node=queue.poll();
sum++;
if(node.left!=null){
queue.offer(node.left);
}
if(node.right!=null){
queue.offer(node.right);
}
}
return sum;
}
}
트리의 깊이 계산(비귀속)
import java.util.Queue;
import java.util.LinkedList;
public class Solution {
public int TreeDepth(TreeNode root) {
if(root==null){
return 0;
}
if(root.left==null&&root.right==null){
return 1;
}
int currentLevelNodes=1; //
int nextLevelNodes=0; //
int depth=0; //
Queue<TreeNode> queue=new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
TreeNode node=queue.poll(); // ， ， queue
currentLevelNodes--;
if(node.left!=null){
queue.offer(node.left);
nextLevelNodes++;
}
if(node.right!=null){
queue.offer(node.right);
nextLevelNodes++;
}
if(currentLevelNodes==0){
currentLevelNodes=nextLevelNodes;
nextLevelNodes=0;
depth++;
}
}
return depth;
}
}
트리의 깊이 계산(귀속)
public class Solution {
public int TreeDepth(TreeNode root) {
if(root==null){
return 0;
}
if(root.left==null&&root.right==null){
return 1;
}
int leftLength=TreeDepth(root.left);
int rightLength=TreeDepth(root.right);
return Math.max(leftLength,rightLength)+1;
}
}
위에서 아래로 나무를 두루 다니다
대기열Queue를 사용하십시오!!
import java.util.Queue;
import java.util.LinkedList;
public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> array=new ArrayList<Integer>();
if(root==null){
return array;
}
Queue<TreeNode> queue=new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()){
TreeNode node=queue.poll();
if(node.left!=null){
queue.offer(node.left);
}
if(node.right!=null){
queue.offer(node.right);
}
array.add(node.val);
}
return array;
}
}
이전 순서 반복 (귀속)
이곳의 함정은
ArrayList array=new ArrayList()； 변수array의 사용에 있다import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> array=new ArrayList<Integer>();
if(root==null){
return array;
}
preorderTraversal(root,array);
return array;
}
public void preorderTraversal(TreeNode root,ArrayList<Integer> array){
if(root==null){
return;
}
array.add(root.val);
preorderTraversal(root.left,array);
preorderTraversal(root.right,array);
}
}
이전 순서 반복 (비귀속)
창고를 사용하면 매 결점에 대해 먼저 오른쪽 노드를 넣은 다음에 왼쪽 노드를 넣은 다음에 창고 꼭대기 요소를 순환해서 꺼내면 모든 왼쪽 트리를 실행해야만 오른쪽 트리를 돌릴 수 있다.
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public ArrayList<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> array=new ArrayList<Integer>();
if(root==null){
return array;
}
Stack<TreeNode> stack=new Stack<TreeNode>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node=stack.pop();
array.add(node.val);
if(node.right!=null){
stack.push(node.right);
}
if(node.left!=null){
stack.push(node.left);
}
}
return array;
}
}
중간 순서로 옮겨다니기 (귀속)
이곳의 함정은
ArrayList array=new ArrayList()； 변수array의 사용에 있다import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> inorderTraversal(TreeNode root) {
ArrayList<Integer> array=new ArrayList<Integer>();
if(root==null){
return array;
}
inorderTraversal(root,array);
return array;
}
public void inorderTraversal(TreeNode root,ArrayList<Integer> array){
if(root==null){
return;
}
inorderTraversal(root.left,array);
array.add(root.val);
inorderTraversal(root.right,array);
}
}
뒷순서 반복 (귀속)
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> postorderTraversal(TreeNode root) {
ArrayList<Integer> array=new ArrayList<Integer>();
if(root==null){
return array;
}
postorderTraversal(root,array);
return array;
}
public void postorderTraversal(TreeNode root,ArrayList<Integer> array){
if(root==null){
return;
}
postorderTraversal(root.left,array);
postorderTraversal(root.right,array);
array.add(root.val);
}
}
두 갈래 트리에서 어떤 값의 경로 (귀속)
public class Solution {
ArrayList<ArrayList<Integer>> array=new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> temp=new ArrayList<Integer>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
if(root==null){
return array;
}
temp.add(root.val);
target-=root.val;
if(target==0&&root.left==null&&root.right==null){
array.add(new ArrayList(temp)); // ArrayList
}
FindPath(root.left,target);
FindPath(root.right,target);
temp.remove(temp.size()-1); //
return array;
}
}
leetCode：sum-root-to-leaf-numbers
제목 설명:
Given a binary tree containing digits from0-9only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path1->2->3which represents the number123.
Find the total sum of all root-to-leaf numbers.
For example,
1
/ \
2 3
The root-to-leaf path1->2represents the number12.
The root-to-leaf path1->3represents the number13.
Return the sum = 12 + 13 =25.
public class Solution {
public int sumNumbers(TreeNode root) {
if(root==null){
return 0;
}
if(root.left==null&&root.right==null){
return root.val;
}
int sum=0;
return sumNumbers(root,sum);
}
public int sumNumbers(TreeNode root,int sum){
if(root==null){
return 0;
}
sum=10*sum+root.val;
if(root.left==null&&root.right==null){ // ， 0
return sum;
}
int sumLeft=sumNumbers(root.left,sum);
int sumRight=sumNumbers(root.right,sum);
return sumLeft+sumRight;
}
}
좋은 문장을 추천하다.
1. 두 갈래 나무 면접 문제 요약
2. 두 갈래 나무 면접문제 leetCode 요약
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[사슴님 Node] Express 프레임워크 설치알다 Express는 최소 규모의 유연성을 유지하는 Node입니다.js 웹 응용 프로그램 개발 프레임워크는 웹과 모바일 응용 프로그램에 강력한 기능을 제공합니다. 설치하다. 우선 Node를 설치했다고 가정해 보세요....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
