Binary Tree & Binary Search Tree)
class Solution {
public TreeNode invertTree(TreeNode root) {
//recursion terminator
//current level processing
//dirll down
if (root == null) {
return null;
}
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
invertTree(root.left);
invertTree(root.right);
return root;
}
}
2. 두 갈래 나무의 거울 여부 판단 [Symmetric Tree]https://leetcode.com/problems/symmetric-tree/description/solution: 귀속, 코드 보기
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return isMirror(root.left, root.right);
}
public boolean isMirror(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null) {
return false;
}
return p.val == q.val && isMirror(p.left,q.right) && isMirror(p.right,q.left);
}
}
3. Valid Binary Search Tree Valid Binary Search Tree solution: 귀속, 각각 root 판단.left ,root,root.right
class Solution {
public boolean isValidBST(TreeNode root) {
// stack &
//
if (root == null) {
return true;
}
Stack stack = new Stack<>();
TreeNode pre = null;
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if (pre != null && root.val <= pre.val) {
return false;
}
pre = root;
root = root.right;
}
return true;
}
}
4. 두 갈래 검색 트리에서 K의 작은 요소 [Kth Smallest Element in a BST]https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/solution: 왼쪽 노드가 루트 노드보다 작고 오른쪽 노드보다 작기 때문에 두 갈래 검색 트리의 특징 중 하나는 중순으로 흐르는 결과가 바로 트리 안의 노드가 작은 순서에서 큰 순서로 출력되는 결과입니다.여기는 교체 형식을 채택하면 우리는 k소노드를 찾을 때 바로 퇴장할 수 있다.
class Solution {
public int kthSmallest(TreeNode root, int k) {
Stack stack = new Stack<>();
while(root != null || !stack.isEmpty()) {
while(root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
if(--k == 0) break;
root = root.right;
}
return root.val;
}
}
5. 두 갈래 나무의 중차 반복solution:stack을 이용하여
class Solution {
public List inorderTraversal(TreeNode root) {
List list = new ArrayList();
if (root == null) {
return list;
}
Stack stack = new Stack();
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
list.add(root.val);
root = root.right;
}
return list;
}
}
6. Maximum Depth of Binary Tree solution: 귀속, 왼쪽 트리 깊이에 오른쪽 트리 깊이
class Solution {
public int maxDepth(TreeNode root) {
//
if (root == null) {
return 0;
}
return Math.max(maxDepth(root.left) , maxDepth(root.right)) + 1;
// Math.max()
}
}
Minium Depth 문제 첨부, 차이점 주의
class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
if (root.left == null && root.right != null) {
return minDepth(root.right) + 1;
}
if (root.left != null && root.right == null) {
return minDepth(root.left) + 1;
}
return Math.min(minDepth(root.left),minDepth(root.right)) + 1;
}
}
7. Convert sorted list to Binary Search Tree solution: 빠른 포인터, 빠른 포인터가 끝났을 때 마침 느린 포인터가 중점까지 간 다음에 중점을 두 갈래 나무의 뿌리 노드로 하고 좌우 양쪽으로 돌아가기 Convert sorted list to Binary Search Tree
class Solution {
public TreeNode sortedListToBST(ListNode head) {
//recurison
if (head == null) {
return null;
}
return toBST(head,null);
}
public TreeNode toBST(ListNode head,ListNode tail) {
ListNode slow = head;
ListNode fast = head;
if (head == tail) {
return null;
}
while (fast != tail && fast.next != tail) {
fast = fast.next.next;
slow = slow.next;
}
TreeNode thead = new TreeNode(slow.val);
thead.left = toBST(head,slow);
thead.right = toBST(slow.next,tail);
return thead;
}
8. Convert Sorted Array to Binary Search Tree Convert Sorted Array to Binary Search Tree solution: 중점을 찾아서 주의해야 할 것은 수조가 두 갈래로 변하는 함수 toBST(nums, 0, nums.length-1), 주의 방법
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
//recursion
if (nums == null) {
return null;
}
return toBST(nums, 0, nums.length - 1);
}
public TreeNode toBST(int[] nums, int start ,int end) {
if (start > end) {
return null;
}
TreeNode thead = new TreeNode(nums[(start + end) / 2]);
thead.left = toBST(nums, start, (start + end) / 2 - 1);
thead.right = toBST(nums, (start + end) / 2 + 1, end);
return thead;
}
}
9.Lowest Common Ancestor of a Binary Search Tree Lowest Common Ancestor of a Binary Search Tree solution: 귀속, 코드 이해
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || p == null || q == null) {
return null;
}
if (p.val < root.val && q.val < root.val) {
return lowestCommonAncestor(root.left, p, q);
}
if (p.val > root.val && q.val > root.val) {
return lowestCommonAncestor(root.right, p, q);
}
return root;
}
}
10.Lowest Common Ancestor of a Binary Tree [Lowest Common Ancestor of a Binary Tree]https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/solution: 기본적인 사고방식은 한 문제와 같다. 단지 이 문제는 일반적인 두 갈래 나무이기 때문에 두 노드와 뿌리 노드의 크기 관계를 비교할 수 없다.아니면 최근 공공자 노드가 좌우자 나무에 나타났는지 판단해야 한다.
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return root;
}
if (root == p || root == q) {
return root;
}
//
//
TreeNode left = lowestCommonAncestor(root.left, p, q) ;
TreeNode right = lowestCommonAncestor(root.right, p, q);
//
if ( left != null && right != null) {
return root;
}
return left != null ? left : right;
}
}
11. 다른 수를 판단하는 자수 [Subtree of Another Tree]https://leetcode.com/problems/subtree-of-another-tree/description/solution: 자나무는 반드시 잎결점에서 시작해야 한다. 중간 부분의 어떤 부분은 자나무라고 할 수 없다. 그러면 우리는 사고방식을 바꾸자. s의 어떤 결점에서 시작하고 t의 모든 구조와 같다. 그러면 문제는 두 나무가 같은지, 즉Same Tree를 판단하는 문제로 바뀌었다. 이 점을 납득하면 코드는 쓰기 쉽다. 귀속으로 매우 간결하게 쓴다. 우리는 먼저 s의 뿌리결점부터 시작한다.t와 비교하면 만약에 두 나무가 완전히 같다면true를 되돌려준다. 그렇지 않으면 각각 s의 왼쪽 결점과 오른쪽 결점에 대해 귀속을 호출하여 다시 한 번 동일한지 판단하고true를 되돌려주면 찾을 수 있음을 나타낸다.
class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
if (s == null) return false;
if (isSame(s, t)) return true;
return isSubtree(s.left, t) || isSubtree(s.right, t);
}
private boolean isSame(TreeNode s, TreeNode t) {
if (s == null && t == null) return true;
if (s == null || t == null) return false;
if (s.val != t.val) return false;
return isSame(s.left, t.left) && isSame(s.right, t.right);
}
}
12. 두 갈래 나무 검지offer 버전solution: 매번에 하나의 결점을 인쇄할 때, 이 결점에 자결점이 있다면, 이 결점의 자결점을 하나의 대열의 끝에 놓는다.다음은 대기열의 머리에서 가장 먼저 대기열에 들어간 결점을 꺼내고 대기열의 모든 결점이 인쇄될 때까지 앞의 인쇄 작업을 반복합니다.
public static void printFromToBottom(BinaryTreeNode root) {
//
if (root != null) {
//
Queue list = new LinkedList<>();
//
list.add(root);
//
BinaryTreeNode curNode;
//
while (!list.isEmpty()) {
//
curNode = list.remove();
//
System.out.print(curNode.value + " ");
// ，
if (curNode.left != null) {
list.add(curNode.left);
}
// ，
if (curNode.right != null) {
list.add(curNode.right);
}
}
}
}
13. 두 갈래 트리를 여러 줄 검지 offer 버전으로 인쇄하기solution: 대기열 구현, 너비 유한 검색, 주석 보기
public static void print(BinaryTreeNode root) {
if (root == null) {
return;
}
List list = new LinkedList<>();
BinaryTreeNode node;
//
int current = 1;
//
int next = 0;
list.add(root);
while (list.size() > 0) {
node = list.remove(0);
current--;
System.out.printf("%-3d", node.val);
if (node.left != null) {
list.add(node.left);
next++;
}
if (node.right != null) {
list.add(node.right);
next++;
}
if (current ==0) {
System.out.println();
current = next;
next = 0;
}
}
}
@
public void levelorder(TreeNode root) { // BFS
Queue queue = new LinkedList<>();
queue.offer(root);
int level = 0;
while (!queue.isEmpty()) {
System.out.printf("Level %d
", level++);
Queue queue2 = new LinkedList<>();
while (!queue.isEmpty()) {
TreeNode top = queue.poll();
System.out.printf("%d ", top.val);
if (top.left != null) queue2.offer(top.left);
if (top.right != null) queue2.offer(top.right);
}
queue = queue2;
}
}
14. 두 갈래 나무를 체인 테이블 솔루션으로 변경: 코드 보기
class Solution {
private TreeNode prev = null;
public void flatten(TreeNode root) {
if (root == null) {
return;
}
flatten(root.right);
flatten(root.left);
root.right = prev;
root.left = null;
prev = root;
}
}
15. 두 갈래 검색 트리 복원 [Recover a Binary Search Tree]https://leetcode.com/problems/recover-binary-search-tree/description/솔루션: 해결 방법은 중간 순서를 이용하여 순서가 틀린 두 가지를 훑어보는 것입니다. 마지막으로 swap하면 됩니다.이 중간의 잘못은 두 개의 점을 교환했기 때문에 큰 것은 앞으로 왔고 작은 것은 뒤로 갔다.그래서 중서가 편리할 때 만나는 첫 번째 순서는 상쇄된 두 개의 node입니다. 큰 것은 틀림없이recovery의 그 중 하나입니다. 기록해야 합니다.또 하나는 온전한 나무를 두루 돌아다니며 마지막 역순의 node를 기록해야 한다.간단하게 말하면 첫 번째 역순점은 기록해야 하고, 마지막 역순점은 기록해야 하며, 마지막 swap은 기록해야 한다.
class Solution {
TreeNode pre;
TreeNode first;
TreeNode second;
public void recoverTree(TreeNode root) {
pre = null;
first = null;
second = null;
inorder(root);
if (first != null && second != null) {
int tmp = first.val;
first.val = second.val;
second.val = tmp;
}
}
public void inorder(TreeNode root) {
if(root == null) {
return;
}
inorder(root.left);
if(pre == null) {
pre = root;//pre
} else {
if(pre.val > root.val) {
if ( first == null) {
first = pre;//
}
second = root;//
}
pre = root;
}
inorder(root.right);
}
}
16. 루트 노드에서 잎 노드까지의 경로를 계산합니다. 이 경로의 합은 상수solution과 같습니다. 분리, 왼쪽 트리 경로는sum-root와 같습니다.val, 또는 오른쪽 트리에서 경로를sum-root와 같은 경로로 찾습니다.val [Path Sum]https://leetcode.com/problems/path-sum/description/
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
}
if (root.val == sum && root.left == null && root.right == null) {
return true;
}
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum -root.val);
}
}
17. 트리의 후속은 LeetCode 버전solution: 창고를 유지하고 그 안에 트리의 노드를 저장합니다.창고에서 나온 노드를 저장할 목록을 유지합니다.
class Solution {
public List postorderTraversal(TreeNode root) {
//
LinkedList ans = new LinkedList<>();
Stack stack = new Stack<>();
if (root == null) return ans;
stack.push(root);
while (!stack.isEmpty()) {
TreeNode cur = stack.pop();
ans.addFirst(cur.val);
if (cur.left != null) {
stack.push(cur.left);
}
if (cur.right != null) {
stack.push(cur.right);
}
}
return ans;
}
}
18. 두 갈래 나무의 다음 노드solution: (제의: 두 갈래 나무와 그 중의 한 결점을 정하고 어떻게 중간 순서가 차례대로 흐르는 다음 결점을 찾습니까? 나무의 결점은 좌우 자결점을 가리키는 두 개의 바늘 이외에 부모 노드를 가리키는 바늘이 있습니다.)만약 결점에 오른쪽 나무가 있다면, 그 다음 결점은 바로 오른쪽 나무의 왼쪽 결점이다.즉, 오른쪽 결점에서 출발하여 왼쪽 결점을 가리키는 지침을 따라 가면 우리는 그 다음 결점을 찾을 수 있다.이어서 우리는 결점에 오른쪽 나무가 없는 상황을 분석했다.만약 결점이 아버지 노드의 왼쪽 자식 결점이라면, 그 다음 결점은 바로 아버지 결점이다.만약 결점이 오른쪽 나무도 없고, 그것도 아버지 결점의 오른쪽 결점이라면, 이런 상황은 비교적 복잡하다.우리는 아버지 노드를 가리키는 바늘을 따라 아버지 결점의 왼쪽 자 결점을 찾을 때까지 계속 위로 올라갈 수 있다.만약 이런 결점이 존재한다면, 이 결점의 부결점은 우리가 찾는 다음 결점이다.
public static BinaryTreeNode getNext(BinaryTreeNode node) {
if (node == null) {
return null;
}
//
BinaryTreeNode target = null;
if (node.right != null) {
target = node.right;
while (target.left != null) {
target = target.left;
}
return target;
} else if (node.parent != null){
target = node.parent;
BinaryTreeNode cur = node;
// ， ，
while (target != null && target.left != cur) {
cur = target;
target = target.parent;
}
return target;
}
return null;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
