leetcode 의 이 진 트 리
1.binary-tree-preorder-traversal
2.binary-tree-postorder-traversal
3.binary-tree-inorder-traversal
4.binary-tree-level-order-traversal
5.binary-tree-zigzag-level-order-traversal
6.binary-tree-level-order-traversal-ii
7.construct-binary-tree-from-preorder-and-inorder-traversal
8.construct-binary-tree-from-inorder-and-postorder-traversal
9. Minimum Depth of Binary Tree
10.maximum-depth-of-binary-tree
11.balanced-binary-tree
12.sum-root-to-leaf-numbers
13.path-sum
14.path-sum-ii
15.binary-tree-maximum-path-sum
16.symmetric-tree
17.same-tree
18.populating-next-right-pointers-in-each-node
19.populating-next-right-pointers-in-each-node-ii
20.unique-binary-search-trees
21.unique-binary-search-trees-ii
22.recover-binary-search-tree
23.validate-binary-search-tree
1.binary-tree-preorder-traversal
제목: 이 진 트 리 의 앞 순 서 를 찾 습 니 다.
분석: 반복 적 으로 실현 되 고 앞 순 서 는 뿌리 결산 점 을 옮 겨 다 니 며 선후 로 오른쪽, 왼쪽 자 나 무 를 스 택 에 눌 렀 다. 이런 방문 순 서 는 '중 좌우', 즉 앞 순 서 를 옮 겨 다 니 는 것 이다.
public ArrayList preorderTraversal(TreeNode root) {
ArrayList list = new ArrayList<>();
if(root == null)
return list;
Stack stack = new Stack();
stack.push(root);
while(!stack.empty()){
TreeNode node = stack.pop();
if(node.right != null)
stack.push(node.right);
if(node.left != null)
stack.push(node.left);
list.add(node.val);
}
return list;
} 2.binary-tree-postorder-traversal
제목: 이 진 트 리 의 뒷 순 서 를 찾 습 니 다.
분석: 반복 적 으로 실현 되 고 앞 순 서 는 뿌리 결산 점 을 옮 겨 다 니 며 선후 로 좌우 서브 나 무 를 스 택 에 누 르 면 이러한 방문 순 서 는 '중 우 좌' 이 고 마지막 에 reverse 를 하면 된다.reverse： list.add(0,node.val);
public ArrayList postorderTraversal(TreeNode root) {
ArrayList list = new ArrayList();
if(root == null)
return list;
Stack s = new Stack();
s.push(root);
while(!s.empty()){
TreeNode node = s.pop();
if(node.left != null)
s.push(node.left);
if(node.right != null)
s.push(node.right);
list.add(0,node.val);// “ ”， list
}
return list;
} 3.binary-tree-inorder-traversal
제목: 이 진 트 리 한 그루 를 주 고 이 나무의 중간 순 서 를 되 돌려 줍 니 다.예 를 들 어 제 시 된 이 진 트 리 는 {1, \ #, 2, 3} 이 고 [1, 3, 2] 로 되 돌아 갑 니 다.
분석: 스 택 으로 이 진 트 리 의 중간 순 서 를 옮 겨 다 니 기
public ArrayList inorderTraversal(TreeNode root) {
ArrayList list = new ArrayList();
if(root == null)
return list;
Stack stack = new Stack();
TreeNode cur = root;
while(! stack.empty() || cur != null){
if(cur != null){
stack.push(cur);
cur = cur.left;
}
else{
cur = stack.pop();
list.add(cur.val);
cur = cur.right;
}
}
return list;
} 4.binary-tree-level-order-traversal
제목: 이 진 트 리 를 지정 하고 이 진 트 리 의 순서 로 옮 겨 다 니 는 결 과 를 되 돌려 줍 니 다.예 를 들 어 주어진 이 진 트 리 {3, 9, 20, \ #, \ #, 15, 7}, 이 이 진 트 리 의 층 차 를 옮 겨 다 니 는 결 과 는 [* 8629], [9, 20], [15, 7] * 8629] 이다.
분석: 검지 offer 면접 문제 32 - 1 참조https://blog.csdn.net/Nibaby9/article/details/104124413
5.binary-tree-zigzag-level-order-traversal
제목: 이 진 트 리 를 지정 하고 이 진 트 리 의 자형 층 차 를 되 돌려 줍 니 다. (왼쪽 에서 오른쪽으로, 다음 층 은 오른쪽 에서 왼쪽으로, 계속 이렇게 교체 합 니 다)예 를 들 어 주어진 이 진 트 리 {3, 9, 20, \ #, \ #, 15, 7}, 이 이 진 트 리 의 자형 층 차 를 옮 겨 다 니 는 결 과 는 [* 8629], [20, 9], [15, 7] * 8629] 이다.
분석: 검지 offer 면접 문제 32 - 2 참조https://blog.csdn.net/Nibaby9/article/details/104124413
6.binary-tree-level-order-traversal-ii
제목: 두 갈래 나 무 를 정 하고 이 두 갈래 나 무 는 밑 에서 꼭대기 까지 층 차 를 옮 겨 다 닌 다. (왼쪽 에서 오른쪽으로, 잎 노드 에서 뿌리 노드 까지 한 층 한 층 씩 옮 겨 다 닌 다) 예 를 들 어 주어진 두 갈래 나 무 는 {3, 9, 20, \ #, \ #, 15, 7} 이다. 이 두 갈래 나 무 는 밑 에서 꼭대기 까지 층 차 를 옮 겨 다 닌 결과 [15, 7] [9, 20], [8629], [3], [8629] 이다.
분석: 역시 원래 의 방법 에 따라 층 차 를 옮 겨 다 니 는 것 이 좋 습 니 다. 다만 각 층 이 옮 겨 다 니 는 결 과 를 결과 집의 맨 앞 에 추가 할 뿐 입 니 다.
public ArrayList> levelOrderBottom(TreeNode root) {
ArrayList> result = new ArrayList();
if(root == null)
return result;
ArrayList list = new ArrayList();
LinkedList queue = new LinkedList();
queue.offer(root);
while(! queue.isEmpty()){
list.clear();
int size = queue.size();
while(size > 0){
TreeNode cur = queue.poll();
size--;
list.add(cur.val);
if(cur.left != null)
queue.offer(cur.left);
if(cur.right != null)
queue.offer(cur.right);
}
result.add(0,new ArrayList(list));
}
return result;
} 7.construct-binary-tree-from-preorder-and-inorder-traversal
제목: 나무의 앞 순서 와 중간 순 서 를 보 여 줍 니 다. 이 두 갈래 나 무 를 만 드 세 요.메모: 트 리 에 중복 되 는 노드 가 존재 하지 않 는 다 고 가정 할 수 있 습 니 다.
분석: 검지 offer 면접 문제 7 참조https://blog.csdn.net/Nibaby9/article/details/104124413
8.construct-binary-tree-from-inorder-and-postorder-traversal
제목: 나무의 중간 순서 와 뒷 순 서 를 보 여 줍 니 다. 이 두 갈래 나 무 를 만 드 세 요.메모: 주어진 트 리 에 중복 되 는 노드 가 존재 하지 않도록 합 니 다.
분석: 같은 순서 로 옮 겨 다 니 고 먼저 옮 겨 다 니 는 구조!!
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(inorder == null || postorder == null || inorder.length != postorder.length || inorder.length == 0)
return null;
return build(inorder,postorder,0,inorder.length-1,0,postorder.length-1);
}
private TreeNode build(int[] inorder, int[] postorder, int instart, int inend,int pstart, int pend) {
if(instart > inend || pstart > pend)
return null;
TreeNode root = new TreeNode(postorder[pend]);
int size = 0;
for(int i = instart;i <= inend;i++){
if(postorder[pend] == inorder[i])
break;
size++;
}
root.left = build(inorder,postorder,instart,instart+size-1,pstart,pstart+size-1);
root.right = build(inorder,postorder,instart+size+1,inend,pstart+size,pend-1);
return root;
}9. Minimum Depth of Binary Tree
제목: 이 진 트 리 의 최소 깊이 를 구 합 니 다.최소 깊이 는 나무의 뿌리 결점 에서 가장 가 까 운 잎 결점 까지 의 가장 짧 은 경로 에서 결점 의 수량 을 가리킨다.
분석: 순환 실현, 왼쪽 나무 와 오른쪽 나무 가 없 는 상황 분석 에 주의 하 세 요. f（x） = 1 + min{ f(left),f(right) }
public int run(TreeNode root) {
if(root == null){
return 0;
}
int left = run(root.left);
int right = run(root.right);
if(left == 0 || right == 0)
return left + right + 1;
return 1 + (left > right ? right :left);
}10.maximum-depth-of-binary-tree
제목: 이 진 트 리 의 최대 깊이 를 구 합 니 다. 최대 깊이 는 나무의 뿌리 결산 점 에서 가장 먼 잎 결산 점 까지 의 가장 긴 경로 에서 결산 점 의 수량 을 말 합 니 다.
분석: 검지 offer 면접 문제 55 참조https://blog.csdn.net/Nibaby9/article/details/104124413
11.balanced-binary-tree
제목: 주어진 이 진 트 리 가 균형 이 맞 는 지 판단 합 니 다.
분석: 검지 offer 면접 문제 55 확장 참조https://blog.csdn.net/Nibaby9/article/details/104124413
12.sum-root-to-leaf-numbers
제목: 숫자 0 - 9 만 포 함 된 이 진 트 리 를 지정 합 니 다. 뿌리 노드 에서 잎 노드 까지 의 모든 경 로 는 하나의 숫자 로 표시 할 수 있 습 니 다.예 를 들 어 뿌리 노드 에서 잎 노드 까지 의 경 로 는 1 - > 2 - > 3 이 고 이 경 로 는 123 으로 대체 합 니 다.뿌리 노드 에서 잎 노드 까지 의 모든 경 로 를 찾 아 표시 하 는 숫자의 합 을 찾 아 라.예 를 들 어 1.뿌리 노드 에서 잎 노드 까지 의 경로 1 - > 2 는 숫자 12 로 대체 하고 뿌리 노드 에서 잎 노드 까지 의 경로 1 - > 3 은 숫자 13 으로 대체 하기 때문에 답 은 12 + 13 = 25 이다.
분석: 주로 매개 변수의 디자인 에 있 습 니 다. 루트 노드 이상 의 합 은 sum = sum * 10 + root. val 입 니 다.마지막 결 과 는 왼쪽 나무의 합 과 오른쪽 나무의 합 이다.
public int sumNumbers(TreeNode root) {
return sumUtil(root,0);
}
private int sumUtil(TreeNode root,int sum) {
if(root == null)
return 0;
sum = sum * 10 + root.val;
if(root.left == null && root.right == null)
return sum;
return sumUtil(root.left,sum) + sumUtil(root.right,sum);
}13.path-sum
제목: 이 진 트 리 와 값 sum 을 지정 하여 뿌리 노드 에서 잎 노드 까지 의 노드 값 의 합 이 sum 과 같은 경로 가 있 는 지 판단 합 니 다.
분석: 귀속 구 해, hasPathSum (root. left, sum - root. val) || hasPathSum(root.right,sum - root.val)
public boolean hasPathSum(TreeNode root, int sum) {
if(root == null)
return false;
if(root.left == null && root.right == null && root.val == sum)
return true;
if(root.left != null && hasPathSum(root.left,sum - root.val))
return true;
if(root.right != null && hasPathSum(root.right,sum - root.val))
return true;
return false;
}14.path-sum-ii
제목: 이 진 트 리 와 값 sum 을 지정 합 니 다. 모든 뿌리 노드 에서 잎 노드 까지 의 노드 값 과 sum 과 같은 경 로 를 찾 으 십시오.
예 를 들 어 다음 과 같은 이 진 트 리 를 드 리 겠 습 니 다. sum = 22, 5 * 8629 ° / * 8629 ° 4 8 * 8629 ° / / * 8629 ° 11 13 4 * 8629 ° / / * 8629 ° 7, 25, 1 로 돌아 갑 니 다.
분석: 재 귀 구 해 는 주로 매개 변수 설정 에 있 습 니 다.
public ArrayList> pathSum(TreeNode root, int sum) {
ArrayList> result = new ArrayList();
if(root == null)
return result;
ArrayList tmp = new ArrayList();
pathSumUtil(root,sum,result,tmp);
return result;
}
private void pathSumUtil(TreeNode root, int sum, ArrayList> result, ArrayList tmp) {
tmp.add(root.val);//
if(root.val == sum && root.left == null && root.right == null)
result.add(new ArrayList(tmp));
if(root.left != null)
pathSumUtil(root.left,sum - root.val,result,tmp);
if(root.right != null)
pathSumUtil(root.right,sum - root.val,result,tmp);
tmp.remove(tmp.size() - 1);// ！！！
} 15.binary-tree-maximum-path-sum
제목: 이 진 트 리 를 지정 합 니 다. 노드 값 과 가장 큰 경로 의 노드 값 의 합 이 얼마 인지 계산 하 십시오.이 경로 의 시작 노드 와 끝 노드 는 이 진 트 리 의 임 의 노드 일 수 있 습 니 다.예 를 들 어 다음 과 같은 이 진 트 리 를 드 리 겠 습 니 다. 1 * 8629 ° / * 8629 ° 23, 돌아 온 결 과 는 6 입 니 다.
분석: 두 개의 최대 치 를 계산 해 야 합 니 다. 하 나 는 현재 노드 아래 의 최대 경로 와 다른 하 나 는 부모 노드 를 연결 하려 면 가장 큰 경로 와.전자 로 전체 국면 을 가장 많이 업데이트 하고 후자 로 재 귀 치 를 되 돌려 주면 된다.
public class Solution {
int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
sumUtil(root);
return max;
}
private int sumUtil(TreeNode root) {
if(root == null)
return 0;
int left = Math.max(0, sumUtil(root.left));
int right = Math.max(0, sumUtil(root.right));
max = Math.max(max, root.val + left + right);
return Math.max(left, right) + root.val;
}
}16.symmetric-tree
제목: 이 진 트 리 한 그루 를 정 하여 기 가 자신의 거울 인지 아 닌 지 를 판단 한다 (즉, 대칭 여 부 를 판단 한다).
분석: 검지 offer 면접 문제 28 참조https://blog.csdn.net/Nibaby9/article/details/104124413
17.same-tree
제목: 이 진 트 리 두 개 를 드 리 겠 습 니 다. 이 진 트 리 두 개가 같은 지 판단 하 는 함 수 를 쓰 십시오.두 개의 이 진 트 리 가 같다 고 판단 하 는 조건 은 두 개의 이 진 트 리 의 구조 가 같 고 같은 노드 에 똑 같은 값 을 가 진 다 는 것 이다.
분석: easy!좌우 나무 가 같은 지 재 귀적 으로 판단 하면 된다.
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null)
return true;
if(p == null || q == null)
return false;
if(p.val != q.val)
return false;
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}18.populating-next-right-pointers-in-each-node
제목: 이 진 트 리 struct TreeLinkNode {TreeLinkNode * left; TreeLinkNode * right; TreeLinkNode * next; }모든 노드 의 next 포인 터 를 채 워 서 오른쪽 형제 노드 를 가 리 킵 니 다. 오른쪽 형제 노드 가 없 으 면 next 포인 터 를 NULL 로 설정 해 야 합 니 다. 초기 에는 모든 next 포인 터 를 NULL 로 설정 합 니 다.
분석: 주어진 나 무 는 이 진 트 리 가 가득 하기 때문에 하나의 결점: 왼쪽 나무의 next 는 오른쪽 나무 이 고 오른쪽 나무의 next 는 next 의 왼쪽 나무 입 니 다.
public void connect(TreeLinkNode root) {
if(root == null)
return;
if(root.left != null && root.right != null)
root.left.next = root.right;
if(root.next != null && root.right != null)
root.right.next = root.next.left;
connect(root.left);
connect(root.right);
}19.populating-next-right-pointers-in-each-node-ii
제목: "Populating Next Right Pointers in Each Node" 를 계속 생각해 보 세 요. 이 문 제 는 주어진 트 리 가 임의의 이 진 트 리 일 수 있다 면 요? 이전에 제시 한 알고리즘 은 아직 유효 합 니까? 주의: 상수 의 추가 메모리 공간 만 사용 할 수 있 습 니 다.
분석: 층 차 를 옮 겨 다 니 지만 옮 겨 다 니 기 전에 새로 만 든 각 층 의 첫 번 째 노드 를 모 의 하여 뒤에 옮 겨 다 니 기 편 하도록 합 니 다.
public void connect(TreeLinkNode root) {
while(root != null){
TreeLinkNode firstNode = new TreeLinkNode(0);
TreeLinkNode cur = firstNode;
while(root != null){
if(root.left != null){
cur.next = root.left;
cur = cur.next;
}
if(root.right != null){
cur.next = root.right;
cur = cur.next;
}
root = root.next;
}
root = firstNode.next;
}
}20.unique-binary-search-trees
제목: 값 n 을 지정 하면 1... n 을 포함 하 는 이 진 트 리 (BST) 를 얼마나 구축 할 수 있 습 니까? 예 를 들 어 주어진 n. = 3, 다섯 가지 다른 이 진 트 리 검색
분석: 동적 계획. 1 차원 배열 dp [i] 는 1... i 숫자 가 몇 가지 이 진 트 리 를 구성 할 수 있 는 지, dp [0] = 1; dp [1] = 1; dp [n] = sum {dp [j] * dp [n - j - 1]}, 0 을 나타 낸다.
public int numTrees(int n) {
if(n < 0)
return 0;
int []dp = new int[n+1];
dp[0] = 1;
dp[1] = 1;
for(int i = 2;i <= n;i++){
for(int j =0;j < i;j++){
dp[i] += dp[j] * dp[i-j-1];
}
}
return dp[n];
}21.unique-binary-search-trees-ii
제목: 값 n 을 지정 합 니 다. 모든 저장 값 1... n. 의 이 진 트 리 (BST) 구 조 를 생 성 하 십시오. 예 를 들 어 주어진 n = 3, 프로그램 은 다섯 가지 다른 이 진 트 리 를 제공 해 야 합 니 다.
분석: i 를 뿌리 로 하 는 모든 왼쪽 나무 와 오른쪽 나 무 를 재 귀적 으로 구 한 다음 에 모든 왼쪽 나무 와 오른쪽 나 무 를 서로 조합 합 니 다.
public ArrayList generateTrees(int n) {
return generateTreesUtil(1,n);
}
private ArrayList generateTreesUtil(int low, int high) {
ArrayList result = new ArrayList();
if (low > high) {
result.add(null);
return result;
}
for(int i = low;i <= high;i++){// i
ArrayList left = generateTreesUtil(low,i-1);
ArrayList right = generateTreesUtil(i+1,high);
for(int j = 0;j < left.size();j++){
for(int k = 0;k < right.size();j++){
TreeNode root = new TreeNode(i);
root.left = left.get(j);
root.right = right.get(k);
result.add(root);
}
}
}
return result;
} 22.recover-binary-search-tree
제목: 이 진 트 리 (BST) 의 두 노드 가 잘못 교환 되 었 습 니 다. 트 리 의 구 조 를 바 꾸 지 않 고 이 나 무 를 복원 하 십시오. 비고: O (n) 의 공간 으로 이 문 제 를 해결 하 는 방법 은 너무 폭력 적 입 니 다. 상수 적 인 공간 복잡 도 알고리즘 을 설계 할 수 있 습 니까?
분석: 두 갈래 검색 트 리 의 순서 가 질서정연 하 게 옮 겨 다 니 며 한 그룹의 질서정연 한 숫자 에 대해 두 개의 숫자 가 잘못 바 뀌 었 습 니 다. 예 를 들 어 1. 2 10 8 9 4 11 12. 첫 번 째 오류 수 는 pre > cur 의 pre 가 처음 나타 나 는 것 이 고, 두 번 째 오류 수 는 pre > cur 의 cur 가 마지막 으로 나타 나 는 것 입 니 다.
public void recoverTree(TreeNode root) {
TreeNode first = null;
TreeNode second = null;
TreeNode pre = null;
if(root == null)
return;
Stack s = new Stack();
TreeNode cur = root;
while(!s.empty() || cur != null){
if(cur != null){
s.push(cur);
cur = cur.left;
}
else{
cur = s.pop();
if(pre != null){
if(pre.val > cur.val) {
if (first == null)
first = pre;
second = cur;
}
}
pre = cur;
cur = cur.right;
}
}
if(first != null && second != null){
int temp = first.val;
first.val = second.val;
second.val = temp;
}
} 23.validate-binary-search-tree
제목: 제 시 된 이 진 트 리 가 이 진 트 리 인지 판단 하기 (BST)
분석: 이 진 트 리 의 순서 적 질서 성 을 이용 하여 이 진 트 리 가 왼쪽 트 리 의 < 뿌리 결산 점 > 오른쪽 트 리 를 만족 시 키 는 것 을 주의 하 십시오. 등호 가 없습니다. [1, 1] BST 가 아 닙 니 다.
public boolean isValidBST(TreeNode root) {
if(root == null)
return true;
TreeNode pre = null;
Stack s = new Stack();
TreeNode cur = root;
while(!s.empty() || cur != null){
if(cur != null){
s.push(cur);
cur = cur.left;
}
else{
cur = s.pop();
if(pre != null){
if(pre.val >= cur.val)
return false;
}
pre = cur;
cur = cur.right;
}
}
return true;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
leetcode 637. 두 갈래 나무의 층 평균치비공 두 갈래 나무를 정하고 각 층 노드의 평균값으로 구성된 그룹을 되돌려줍니다. 예 1: 참고: 노드 값의 범위는 32비트 기호 정수 범위 내에.....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
