当前位置:网站首页>Binary tree high frequency question type
Binary tree high frequency question type
2022-07-07 09:24:00 【Fly upward】
Catalog
1. The number of nodes in a complete binary tree
3. For the first K The number of layer nodes
4. The maximum depth of a binary tree
5. Find binary tree value Whether there is
6. Whether it is a complete binary tree
8. The subtree of another tree
11. Sequence traversal of binary tree
12. The nearest common ancestor of a binary search tree
13. Binary search tree Convert to a sorted two-way linked list
1. The number of nodes in a complete binary tree
Here's a tree for you Perfect binary tree The root node root , Find out the number of nodes of the tree .
Perfect binary tree Is defined as follows : In a complete binary tree , Except that the lowest node may not be full , The number of nodes in each layer reaches the maximum , And the nodes of the lowest layer are concentrated in the leftmost positions of the layer . If the bottom layer is No h layer , Then the layer contains 1~ 2h Nodes .
Title source : Power button (LeetCode)
link :https://leetcode.cn/problems/count-complete-tree-nodes
class Solution {
//1. Traversal ideas
int count = 0;
public int countNodes1(TreeNode root) {
if (root == null){
return 0;
}
count++;
countNodes(root.left);
countNodes(root.right);
return count;
}
//2 Sub problem ideas
public int countNodes(TreeNode root) {
if (root == null){
return 0;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
2. Number of leaf nodes
//1. Traversal ideas
int leafCount = 0;
int getLeafNodeCount1(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
leafCount++;
}
getLeafNodeCount(root.left);
getLeafNodeCount(root.right);
return leafCount;
}
//2. Sub problem ideas
int getLeafNodeCount(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
}
3. For the first K The number of layer nodes
/**
* For the first K The number of layer nodes
* Sub problem ideas
*/
int GetKLeveNodeCount(TreeNode root, int k) {
if (root == null) {
return 0;
}
if (k == 1) {
return 1;
}
return GetKLeveNodeCount(root.left, k-1) + GetKLeveNodeCount(root.right, k-1);
}
4. The maximum depth of a binary tree
Given a binary tree , Find out the maximum depth .
The depth of a binary tree is the number of nodes in the longest path from the root node to the farthest leaf node .
explain : A leaf node is a node that has no children .
Title source : Power button (LeetCode)
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return leftDepth > rightDepth ? leftDepth+1 : rightDepth+1;
}
5. Find binary tree value Whether there is
TreeNode find(TreeNode root,char val) {
if (root == null) {
return null;
}
if (root.val == val) {
return root;
}
TreeNode ret = final (root.left, val);
if (ret != null) {
return ret;
}
ret = final (root.right, val);
if (ret != null) {
return ret;
}
return null;
}
6. Whether it is a complete binary tree
boolean isCompleteTree(TreeNode root) {
if (root == null) {
return true;
}
Queue<TreeNode> queue = new LinkedList;
// In the queue
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
if (cur != null) {
queue.offer(left);
queue.offer(right);
}else {
break;
}
}
// Outgoing queue
while (!queue.isEmpty()) {
TreeNode top = queue.peek();
if (top != null) {
return false;
}
queue.poll();
}
return true;
}
7. Same tree
Here are the root nodes of two binary trees p
and q
, Write a function to check whether the two trees are the same .
If two trees are the same in structure , And the nodes have the same value , They are the same .
Title source : Power button (LeetCode)
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q != null || p != null && q == null) {
return false;
}
if (p == null && q == null) {
return true;
}
if (q.val != p.val) {
return false;
}
return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
8. The subtree of another tree
Here are two binary trees root and subRoot . test root Whether and subRoot Subtrees with the same structure and node values . If there is , return true ; otherwise , return false .
Binary tree tree A subtree of includes tree A node of and all descendants of this node .tree It can also be seen as a subtree of its own .
Title source : Power button (LeetCode)
link :https://leetcode.cn/problems/subtree-of-another-tree
public boolean isSubtree(TreeNode root,TreeNode subRoot) {
if (root == null || subRoot == null) {
return false;
}
// Root node and subroot Are there two same trees
if (isSameTree(root,subRoot)) {
return true;
}
//subRoot Is it right? root The left subtree
if (isSubtree(root.left,subRoot)) {
return true;
}
if (isSubtree(root.right,subRoot)) {
return true;
}
return false;
}
9. Balanced binary trees
Given a binary tree , Determine if it's a highly balanced binary tree .
In this question , A height balanced binary tree is defined as :
A binary tree Every node The absolute value of the height difference between the left and right subtrees is not more than 1
Title source : Power button (LeetCode)
Solution 1
//1. First check the depth
public int height(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = height(root.left);
int rightHeight = height(root.right);
return (leftHeight > rightHeight) ? (leftHeight + 1) : (rightHeight + 1);
}
//2. Check the depth difference between the left and right subtrees 1 Is balanced
public boolean isBalance(TreeNode root) {
if (root == null) {
return true;
}
int left = height(root.left);
int right = height(root.right);
return Math.abs(left - right) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
Solution 2
public int height(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = height(root.left);
int rightHeight = height(root.right);
if (leftHeight >= 0 && rightHeight >= 0 && Math.abs(leftHeight-rightHeight) <= 1) {
return Math.max(leftHeight,rightHeight) + 1;
}else {
// Explain the imbalance
return -1;
}
}
public boolean isBalance(TreeNode root) {
if (root == null) {
return true;
}
return height(root) >= 0;
}
10. Symmetric binary tree
Give you the root node of a binary tree root
, Check whether it is axisymmetric .
Title source : Power button (LeetCode)
public boolean isSymmetricChild(TreeNode leftTree, TreeNode rightTree) {
if (leftTree == null && rightTree != null) return false;
if (leftTree != null && rightTree == null) return false;
if (leftTree == null && rightTree == null) return true;
if (leftTree.val != rightTree.val) return false;
return isSymmetricChild(leftTree.left,rightTree.right) &&
isSymmetricChild(leftTree.right,rightTree.left);
}
public boolean isSymmetric(TreeNode root) {
if (root == null) {
return true;
}
return isSymmetricChild(root.left ,root.right);
}
11. Sequence traversal of binary tree
Give you the root node of the binary tree root
, Returns the Sequence traversal . ( That is, layer by layer , Access all nodes from left to right )
Title source : Power button (LeetCode)
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<>();
if (root == null) return ret;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty) {
int size = queue.size();// How many nodes are there in the current layer
List<Integer> lst = new ArrayList<>();
while (size != 0) {
TreeNode cur = queue.poll();
list.add(cur.val);
if (cur.left != null) {
queue.offer(cur.left);
}
if (cur.right != null) {
queue.offer(cur.right);
}
size--;
}
ret.add(list);
}
return ret;
}
12. The nearest common ancestor of a binary search tree
Given a binary tree , Find the nearest common ancestor of the two specified nodes in the tree .
In Baidu Encyclopedia, the most recent definition of public ancestor is :“ For a tree T Two nodes of p、q, Recently, the common ancestor is represented as a node x, Satisfy x yes p、q Our ancestors and x As deep as possible ( A node can also be its own ancestor ).
source : Power button (LeetCode)
link :https://leetcode.cn/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (`root == null) {
return null;
}
if (root == p || root == q) {
return root;
}
TreeNode leftT = lowestCommonAncestor(root.left,p,q);
TreeNode rightT = lowestCommonAncestor(root.right,p,q);
if (leftT != null && rightT != null) {
return root;
}else if (leftT != null) {
return leftT;
}else {
return rightT;
}
}
13. Binary search tree Convert to a sorted two-way linked list
TreeNode prev = null;
public void inorder(TreeNode pCur) {
if (pCur == null) {
return;
}
inorder(pCur.left);
pCur.left = prev;
if (prev != null) {
prev.right = pCur;
}
prev = pCur;
inorder(pCur.right);
}
public TreeNode Convert(TreeNode pRootOfTree) {
if (pRootOfTree == null) {
return null;
}
inorder(pRootOfTree);
TreeNode head = pRootOfTree;
while (head.left != null) {
head = head.left;
}
return head;
}
边栏推荐
- Summary of PMP learning materials
- Where is the answer? action config/Interceptor/class/servlet
- 正则匹配以XXX开头的,XXX结束的
- Interface test API case, data and interface separation
- Cesium does not support 4490 problem solution and cesium modified source code packaging scheme
- Storage of data in memory
- Why is access to the external network prohibited for internal services of the company?
- 数据库多表关联查询问题
- What is the value of getting a PMP certificate?
- Pick up the premise idea of programming
猜你喜欢
Confitest of fixture py
stm32和电机开发(从单机版到网络化)
嵌套(多级)childrn路由,query参数,命名路由,replace属性,路由的props配置,路由的params参数
信息安全实验二 :使用X-SCANNER扫描工具
How to speed up video playback in browser
NATAPP内网穿透
【SVN】SVN是什么?怎么使用?
Postman interface test (I. installation and use)
Postman data driven
Variable parameter of variable length function
随机推荐
Summary of PMP learning materials
What is the value of getting a PMP certificate?
What are the suggestions for PMP candidates?
Huawei hcip datacom core_ 03day
Pytest installation (command line installation)
Colorbar of using vertexehelper to customize controls (II)
消费互联网的产业链其实是很短的,它仅仅承接平台上下游的对接和撮合的角色
Netease Cloud Wechat applet
超十万字_超详细SSM整合实践_手动实现权限管理
在EXCEL写VBA连接ORACLE并查询数据库中的内容
Nested (multi-level) childrn routes, query parameters, named routes, replace attribute, props configuration of routes, params parameters of routes
C language pointer (exercises)
C language pointer (Part 2)
How does the project manager write the weekly summary and weekly plan?
MySql数据库-事务-学习笔记
Yapi test plug-in -- cross request
Locust performance test 5 (analysis)
Cesium does not support 4490 problem solution and cesium modified source code packaging scheme
Leetcode question brushing record (array) combination sum, combination sum II
Information Security Experiment 2: using x-scanner scanning tool