LeetCode - 두 갈래 나무 총결산(1)
53504 단어 coding
두 갈래 나무
두 갈래 나무는 빈 나무이거나 자결점을 가리키는 바늘이 있고, 바늘마다 나무를 가리킨다.나무는 일종의 귀속 구조로 많은 나무의 문제는 귀속으로 처리할 수 있다.
나무 높이
104. Maximum Depth of Binary Tree (Easy)
class Solution {
public int maxDepth(TreeNode root) {
if (null == root) {
return 0;
}
if (null == root.left && null == root.right) {
return 1;
}
int leftHeight = 0;
int rightHeight = 0;
if (root.left != null) {
leftHeight = maxDepth(root.left) + 1;
}
if (root.right != null) {
rightHeight = maxDepth(root.right) + 1;
}
return leftHeight > rightHeight ? leftHeight : rightHeight;
}
}
평형수
110. Balanced Binary Tree (Easy)
3
/ \
9 20
/ \
15 7
평형수 좌우자 나무의 높이 차이는 모두 1보다 작다
class Solution {
boolean flag = true;
public boolean isBalanced(TreeNode root) {
if (null == root) {
return true;
}
maxDepth(root);
return flag;
}
public int maxDepth(TreeNode root) {
if (null == root) {
return 0;
}
if (null == root.left && null == root.right) {
return 1;
}
int left = 0;
int right = 0;
left = maxDepth(root.left) + 1;
right = maxDepth(root.right) + 1;
if (Math.abs(left - right) > 1) {
flag = false;
}
return left > right ? left : right;
}
}
두 노드의 최장 경로
543. Diameter of Binary Tree (Easy)
Input:
1
/ \
2 3
/ \
4 5
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
class Solution {
int max = Integer.MIN_VALUE;
public int diameterOfBinaryTree(TreeNode root) {
if (null == root) {
return 0;
}
int left = maxDepth(root.left);
int right = maxDepth(root.right);
max = Math.max(max, left + right);
diameterOfBinaryTree(root.left);
diameterOfBinaryTree(root.right);
return max;
}
public int maxDepth(TreeNode root) {
if (null == root) {
return 0;
}
if (null == root.left && null == root.right) {
return 1;
}
int left = maxDepth(root.left) + 1;
int right = maxDepth(root.right) + 1;
return left > right ? left : right;
}
}
나무를 뒤집다
226. Invert Binary Tree (Easy)
class Solution {
public TreeNode invertTree(TreeNode root) {
if (null == root) {
return null;
}
TreeNode left = root.left;
root.left = invertTree(root.right);
root.right = invertTree(left);
return root;
}
}
두 그루의 나무를 합치다
617. Merge Two Binary Trees (Easy)
Input:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
Output:
3
/ \
4 5
/ \ \
5 4 7
class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if (null == t1 && null == t2) {
return null;
}
if (null == t1) {
return t2;
}
if (null == t2) {
return t1;
}
t1.val += t2.val;
t1.left = mergeTrees(t1.left, t2.left);
t1.right = mergeTrees(t1.right, t2.right);
return t1;
}
}
경로와 동일한지 여부를 판단하다
Leetcdoe : 112. Path Sum (Easy)
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
루트에서 leaf까지의 모든 노드의 합을 경로와 정의합니다.
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (null == root) {
return false;
}
if (sum == root.val && null == root.left && null == root.right) {
return true;
}
boolean left = false;
boolean right = false;
if (root.left != null) {
left = hasPathSum(root.left, sum - root.val);
}
if (root.right != null) {
right = hasPathSum(root.right, sum - root.val);
}
return left | right;
}
}
경로 및 동일한 경로 수 통계
437. Path Sum III (Easy)
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
Return 3. The paths that sum to 8 are:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11
경로가 루트로 시작하거나 leaf로 끝나는 것은 아니지만 연속해야 합니다.
class Solution {
public int pathSum(TreeNode root, int sum) {
if (null == root) {
return 0;
}
int num = help(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
return num;
}
public int help(TreeNode root, int sum) {
if (null == root) {
return 0;
}
int ret = 0;
if (sum == root.val) {
ret++;
}
ret += help(root.left, sum - root.val) + help(root.right, sum - root.val);
return ret;
}
}
자목
572. Subtree of Another Tree (Easy)
Given tree s:
3
/ \
4 5
/ \
1 2
Given tree t:
4
/ \
1 2
Return true, because t has the same structure and node values with a subtree of s.
Given tree s:
3
/ \
4 5
/ \
1 2
/
0
Given tree t:
4
/ \
1 2
Return false.
class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
if (null == s && null == t) {
return true;
}
if (null == s || null == t) {
return false;
}
boolean left = false;
boolean right = false;
if (null == s.left && null == s.right) {
return help(s, t);
}
if (s.left != null) {
left = help(s, t) || isSubtree(s.left, t);
}
if (s.right != null) {
right = help(s, t) || isSubtree(s.right, t);
}
return left || right;
}
public boolean help(TreeNode s, TreeNode t) {
if (null == s && null == t) {
return true;
}
if (null == s || null == t) {
return false;
}
if (s.val != t.val) {
return false;
}
return help(s.left, t.left) && help(s.right, t.right);
}
}
나무의 대칭
101. Symmetric Tree (Easy)
1
/ \
2 2
/ \ / \
3 4 4 3
class Solution {
public boolean isSymmetric(TreeNode root) {
if (null == root) {
return true;
}
if (null == root.left && null == root.right) {
return true;
}
if (null == root.left || null == root.right) {
return false;
}
if (root.left.val != root.right.val) {
return false;
}
return help(root.left.left, root.right.right) && help(root.left.right, root.right.left);
}
public boolean help(TreeNode t1, TreeNode t2) {
if (null == t1 && null == t2) {
return true;
}
if (null == t1 || null == t2) {
return false;
}
if (t1.val != t2.val) {
return false;
}
return help(t1.left, t2.right) && help(t1.right, t2.left);
}
}
최소 경로
111. Minimum Depth of Binary Tree (Easy)
나무의 뿌리 노드에서 잎 노드까지의 최소 경로 길이
class Solution {
public int minDepth(TreeNode root) {
if (null == root) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int level = 1;
while (!queue.isEmpty()) {
int size = queue.size();
while (size > 0) {
TreeNode node = queue.poll();
if (null == node.left && null == node.right) {
return level;
}
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
size--;
}
level++;
}
return level;
}
}
왼쪽 잎 노드의 합을 통계하다
404. Sum of Left Leaves (Easy)
3
/ \
9 20
/ \
15 7
There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.
class Solution {
int sum = 0;
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left != null) {
if (null == root.left.left && null == root.left.right) {
sum += root.left.val;
}
sumOfLeftLeaves(root.left);
}
if (root.right != null) {
sumOfLeftLeaves(root.right);
}
return sum;
}
}
동일한 노드 값의 최대 경로 길이
687. Longest Univalue Path (Easy)
1
/ \
4 5
/ \ \
4 4 5
Output : 2
class Solution {
int max = 0;
public int longestUnivaluePath(TreeNode root) {
if (null == root) {
return 0;
}
dfs(root);
return max;
}
public int dfs(TreeNode root) {
if (null == root) {
return 0;
}
int left = dfs(root.left);
int right = dfs(root.right);
if (root.left != null && root.left.val == root.val) {
left++;
} else {
left = 0;
}
if (root.right != null && root.right.val == root.val) {
right++;
} else {
right = 0;
}
max = Math.max(max, left + right);
return Math.max(left, right);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
반응-Redux_폴더 구조:- _ Index.js App.js Counter.js counterSlice.js coin.js theme.js themeSlice.js store.js 사진 출력 감사합니다. 다음에서 팔로우할 수 있...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
