Careercup | Chapter 4
19824 단어 apt
완전 두 갈래 나무는 마지막 층을 제외하고 각 층의 노드 수가 모두 최대치에 달한다.마지막 층에 오른쪽의 약간의 결점만 부족하다.complete binary tree
두 갈래 나무가 가득 차서 완벽한 두 갈래 나무는 모든 결점수가 가장 큰 두 갈래 나무다.perfect binary tree, full binary tree.
균형 잡힌 두 갈래 나무, 좌우 자목의 높이는 일정한 범위 내에 있다.
두 갈래 검색 트리(Binary Search Tree)는 두 갈래 검색 트리, 질서정연한 두 갈래 트리(ordered binary tree), 두 갈래 트리(sorted binary tree)라고도 하는데 빈 나무 또는 아래의 성질을 가진 두 갈래 트리를 가리킨다.
두 갈래에서 트리를 찾아 결점을 삭제하고 세 가지 상황으로 나누어 토론한다.
4.1 Implement a function to check if a binary tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that the heights of the two subtrees of any node never differ by more than one.
점이것 .
4.2 Given a directed graph, design an algorithm to find out whether there is a route between two nodes.
BFS나 DFS만 있으면 되지만 BFS는 한 경로에서 너무 깊게 파는 것을 피할 수 있습니다.
4.3 Given a sorted (increasing order) array with unique integer elements, write an algorithm to create a binary search tree with minimal height
점이것 .
4.4 Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth (e.g., if you have a tree with depth D, you'll have D linked lists).
BFS 또는 DFS 모두 가능합니다.주의할 점은 DFS는 별도의 O(lgn) 스택 공간을 사용하지만 전체적인 공간 복잡도는 O(n)입니다.
4.5 Implement a function to check if a binary tree is a binary search tree.
점이것 .BST는 중간 순서와 함께 연결되어야 한다.
4.6 Write an algorithm to find the 'next'node (i.e., in-order successor) of a given node in a binary search tree. You may assume that each node has a link to its parent.
루트 결점이 있다면pre 결점을 직접 중순으로 반복해서 기록하면 됩니다.만약 결점만 있다면, 상황을 나누어야 한다.
4.7 Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not necessarily a binary search tree.
leetcode의 박문은 매우 자세하게 말한다.이 문제는 매우 고전적이다. 특히parent 결점이 있을 때의 해법은 intersectlinklist의 교차점을 구하는 것과 유사하다.
4.8 You have two very large binary trees: Tl, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of Tl. A tree T2 is a subtree of Tl if there exists a node n in Tl such that the subtree of n is identical to T2. That is, if you cut off the tree at node n, the two trees would be identical.
이 문제는 샅샅이 뒤질 수도 있고pre-order와 in-order의travesal 문자열을 바탕으로 하위 문자열로 찾을 수도 있다.
4.9 You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum to a given value. The path does not need to start or end at the root or a leaf.
샅샅이 뒤질 수밖에 없다.
1 struct TreeNode {
2 TreeNode *left;
3 TreeNode *right;
4 TreeNode *parent;
5 int val;
6 TreeNode(int v):val(v),left(NULL),right(NULL),parent(NULL) {}
7 };
8
9 // 4.6
10 TreeNode* findInorderNext(TreeNode* node) {
11 if (node == NULL) {
12 return NULL;
13 } else if (node->right) {
14 node = node->right;
15 while (node->left) node = node->left;
16 return node;
17 } else {
18 while (node->parent && node->parent->left != node) node = node->parent;
19 return node->parent;
20 }
21 }
22
23 TreeNode* findPreordeNext(TreeNode* node) {
24 if (node == NULL) {
25 return NULL;
26 } else if (node->left) {
27 return node->left;
28 } else if (node->right) {
29 return node->right;
30 } else {
31 while (node->parent && node->parent->right == node) {
32 node = node->parent;
33 }
34 if (node->parent) return node->parent->right;
35 else return NULL;
36 }
37 }
38
39 TreeNode* findPostorderNext(TreeNode* node) {
40 if (node == NULL || node->parent == NULL) {
41 return NULL;
42 } else if (node->parent->right == node || node->parent->right == NULL) { // right subtree
43 return node->parent;
44 } else {
45 node = node->parent->right;
46 while (node->left) node = node->left;
47 return node;
48 }
49 }
50
51
52 // 4.7 (1) p, q in the BST, O(h) runtime
53 TreeNode* LCAInBST(TreeNode *root, TreeNode *p, TreeNode *q) {
54 if (!root || !p || !q) return NULL;
55 if (max(p->val, q->val) < root->val) {
56 return LCAInBST(root->left, p, q);
57 } else if (min(p->val, q->val) > root->val) {
58 return LCAInBST(root->right, p, q);
59 } else {
60 return root;
61 }
62 }
63
64 // 4.7 (2.1) p, q may not in the tree, this is just a binary tree
65 int matchCount(bool pExisted, bool qExisted) {
66 int m = 0;
67 if (pExisted) m++;
68 if (qExisted) m++;
69 return m;
70 }
71 TreeNode* LCAInBT(TreeNode *root, TreeNode *p, TreeNode *q, bool &pExisted, bool &qExisted) {
72 if (!root) return NULL;
73
74 TreeNode* ret = LCAInBT(root->left, p, q, pExisted, qExisted);
75 int lm = matchCount(pExisted, qExisted);
76 if (lm == 2) return ret; // p, q are in the left subtree
77 ret = LCAInBT(root->right, p, q, pExisted, qExisted);
78 int rm = matchCount(pExisted, qExisted);
79 if (rm == 2) { // p, q are found
80 if (lm == 1) return root; //p, q are in different subtree, thus return root
81 else return ret; // lm == 0, p, q are in the right subtree
82 }
83 if (root == p) pExisted = true;
84 if (root == q) qExisted = true;
85 if (pExisted && qExisted) return root; // if q is a child of q (or, q is a child of p)
86 return NULL; // if p or q is not existed
87 }
88
89 // 4.7(2.2) the parent node is available
90 int getHeight(TreeNode* p) {
91 int h = 0;
92 while (p) {
93 p = p->parent;
94 h++;
95 }
96 return h;
97 }
98
99 TreeNode* LCAInBT(TreeNode *p, TreeNode *q) {
100 if (!p || !q) return NULL;
101 int h1 = getHeight(p);
102 int h2 = getHeight(q);
103 if (h1 > h2) {
104 swap(p, q);
105 swap(h1, h2);
106 }
107 for (int i = 0; i < h2 - h1; ++i) {
108 q = q->parent;
109 }
110
111 while (p && q) {
112 if (p == q) return p;
113 p = p->parent;
114 q = q->parent;
115 }
116 return NULL;
117 }이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Raspbian에 Ubuntu 용 PPA 추가Raspbian에서 Ubuntu 용 개인 패키지 아카이브 (PPA)를 사용하는 방법을 보여줍니다. Ubuntu 환경이라면 add-apt-repository를 사용하면 리포지토리를 추가 할 수 있어야하지만 Raspbi...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
