当前位置：网站首页>Brush questions --- binary tree --2
Brush questions --- binary tree --2
2022-07-02 12:08:00 【The dishes are not right】
Balanced binary trees
Their thinking ：
Every node of a binary tree The absolute value of the height difference between the left and right subtrees is not more than 1 . Our tips have been given in the title , We need to find the height of the left subtree first , In finding the height of the right subtree , Then look at their height difference .
int getHeight(TreeNode root){
if(root==null){
return 0;
}
int lightLeft=getHeight(root.left);
int lightRight=getHeight(root.right);
return lightLeft>lightRight?lightLeft+1:lightRight+1;
}
public boolean isBalanced(TreeNode root) {
if(root==null){
return true;
}
int left=getHeight(root.left);
int right=getHeight(root.right);
if(Math.abs(left-right)<=1&&isBalanced(root.left)&&isBalanced(root.right)){
return true;
}
return false;
}
There is another way that we can judge whether the absolute value of the height difference between the left and right subtrees exceeds 1, If exceeded 1 Just return a negative number , So if the final result returns a negative number , Then this tree is not a balanced binary tree .
private int getHeight1(TreeNode root){
if(root==null){
return 0;
}
int lightLeft=getHeight(root.left);
int lightRight=getHeight(root.right);
if(lightLeft>=0 && lightRight>=0 && Math.abs(lightLeft- lightRight)<=1){
return Math.max(lightLeft,lightRight)+1;
}else{
return -1;
}
}
public boolean isBalanced1(TreeNode root) {
if(root==null){
return true;
}
return getHeight1(root)>=0;
}
Symmetric binary tree
Their thinking ：
public boolean isSymmetricChild(TreeNode rightTree,TreeNode leftTree){
if(leftTree==null && rightTree!=null) return false;
if(leftTree!=null && rightTree==null) return false;
if(leftTree==null && rightTree==null) return true;
if(rightTree.val!=leftTree.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);
}
Binary tree traversal
Their thinking ： The title gives the result of preorder traversal , So when we build this binary tree , It also needs to be built in the way of preorder traversal .
import java.util.*;
class TreeNode{
public char val;
public TreeNode left;
public TreeNode right;
public TreeNode(char val){
this.val=val;
}
}
public class Main{
public static int i = 0 ;
public static TreeNode createTree(String str) {
TreeNode root = null;
if(str.charAt(i) != '#') {
root = new TreeNode(str.charAt(i));
i++;
root.left = createTree(str);
root.right = createTree(str);
}else {
// encounter # It's an empty tree
i++;
}
return root;
}
public static void inorder(TreeNode root) {
if(root == null) {
return;
}
inorder(root.left);
System.out.print(root.val+" ");
inorder(root.right);
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// Be careful hasNext and hasNextLine The difference between
while (in.hasNextLine()) {
// Note multiple inputs
String str = in.nextLine();
TreeNode root = createTree(str);
inorder(root);
}
}
}
The nearest common ancestor of a binary tree
Their thinking ：
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null) return null;
if(p==root || q==root){
return root;
}
TreeNode left=lowestCommonAncestor(root.left,p,q);
TreeNode right=lowestCommonAncestor(root.right,p,q);
if(left!=null && right!=null){
return root;
}else if(left==null && right!=null){
return right;
}else if(left!=null && right==null){
return left;
}
return null;
}
There's a second way ：
public boolean getPath(TreeNode root,TreeNode node,Stack<TreeNode> stack){
if(root==null || node==null) return false;
stack.push(root);
if(root==node) return true;
boolean flg=getPath(root.left,node,stack);
if(flg){
return true;
}
boolean flg1=getPath(root.right,node,stack);
if(flg1){
return true;
}
stack.pop();
return false;
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null) return null;
Stack<TreeNode> stack1=new Stack<>();
getPath(root,p,stack1);
Stack<TreeNode> stack2=new Stack<>();
getPath(root,q,stack2);
int size1=stack1.size();
int size2=stack2.size();
if(size1-size2>0){
int size=size1-size2;
while(size!=0){
stack1.pop();
size--;
}
while(!stack1.isEmpty() && !stack2.isEmpty()){
if(stack1.peek()==stack2.peek()){
return stack1.pop();
}else{
stack1.pop();
stack2.pop();
}
}
}else{
int size=size2-size1;
while(size!=0){
stack2.pop();
size--;
}
while(!stack1.isEmpty() && !stack2.isEmpty()){
if(stack1.peek()==stack2.peek()){
return stack1.pop();
}else{
stack1.pop();
stack2.pop();
}
}
}
return null;
}
Binary search tree and double linked list
Their thinking ：
TreeNode pre=null;
public void inorder (TreeNode root){
if(root==null) return;
inorder(root.left);
root.left=pre;
if(pre!=null){
pre.right=root;
}
pre=root;
inorder(root.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;
}
Construction of binary trees from traversal sequences of preorder and middle order
Their thinking ：
public int index=0;
public TreeNode createTreeByPandI(int[] preorder, int[] inorder,int inbegin,int inend){
if(inbegin>inend) return null;
TreeNode root=new TreeNode(preorder[index]);
// Find the position of the root node traversed in the middle order
int rootindex=findIndex(inorder,inbegin,inend,preorder[index]);
if(rootindex==-1){
return null;
}
index++;
// Create left subtree and right subtree
root.left=createTreeByPandI(preorder,inorder,inbegin,rootindex-1);
root.right=createTreeByPandI(preorder,inorder,rootindex+1,inend);
return root;
}
public int findIndex(int[] inorder,int inbegin,int inend,int key){
for(int i=inbegin;i<=inend;i++){
if(key==inorder[i]){
return i;
}
}
return -1;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(inorder==null ||preorder==null) return null;
return createTreeByPandI(preorder,inorder,0,inorder.length-1);
}
Construct binary tree from middle order and post order traversal sequence
Their thinking ：
The implementation method is roughly the same as the above question , But pay attention to the order in which the left and right subtrees are created .
public int index = 0;
public TreeNode createTreeByPandI(int[] postorder, int[] inorder,int inbegin,int inend){
if(inbegin>inend) return null;
TreeNode root=new TreeNode(postorder[index]);
// Find the position of the root node traversed in the middle order
int rootindex=findIndex(inorder,inbegin,inend,postorder[index]);
if(rootindex==-1){
return null;
}
index--;
// Create left subtree and right subtree
root.right=createTreeByPandI(postorder,inorder,rootindex+1,inend);
root.left=createTreeByPandI(postorder,inorder,inbegin,rootindex-1);
return root;
}
public int findIndex(int[] inorder,int inbegin,int inend,int key){
for(int i=inbegin;i<=inend;i++){
if(key==inorder[i]){
return i;
}
}
return -1;
}
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(inorder==null ||postorder==null) return null;
index=postorder.length-1;
return createTreeByPandI(postorder,inorder,0,inorder.length-1);
}
Create a string from a binary tree
Their thinking ： Here we use StringBuilder Store string , It will be more convenient and simple . Look at examples to find rules , When to add "(“, When to add ”)“, When to add ”()", It depends on whether the left subtree and the right subtree are empty .
public void treeToString(TreeNode root,StringBuilder sb){
if(root==null) return;
sb.append(root.val);
if(root.left!=null){
sb.append("(");
treeToString(root.left,sb);
sb.append(")");
}else{
if(root.right!=null){
sb.append("()");
}else{
return;
}
}
if(root.right==null){
return;
}else{
sb.append("(");
treeToString(root.right,sb);
sb.append(")");
}
}
public String tree2str(TreeNode root) {
if(root==null) return null;
StringBuilder sb=new StringBuilder();
treeToString(root,sb);
return sb.toString();
}
Preorder traversal of two tree 、 In the sequence traversal 、 Subsequent traversal （ Non recursive implementation ）
Their thinking ： The former sequence traversal : Traverse from root , First traverse the left subtree , Put the traversal result on the stack , After traversing the left subtree , Pop up top element , If the element at the top of the stack has a right subtree, continue to traverse , Do not continue to pop up the next element . So circular , Until you walk through the whole tree . Middle order ergodic isomorphism . Post order traversal requires a little processing , Because if you don't deal with , Will repeat traversal .
// The former sequence traversal
public List<Integer> preorderTraversal(TreeNode root) {
Stack<TreeNode> stack=new Stack<>();
List<Integer> ret=new ArrayList<>();
TreeNode cur=root;
while(cur!=null || !stack.isEmpty()){
while(cur!=null){
stack.push(cur);
ret.add(cur.val);
cur=cur.left;
}
TreeNode top=stack.pop();
cur=top.right;
}
return ret;
}
// In the sequence traversal
public List<Integer> inorderTraversal(TreeNode root) {
Stack<TreeNode> stack=new Stack<>();
List<Integer> ret=new ArrayList<>();
TreeNode cur=root;
while(cur!=null || !stack.isEmpty()){
while(cur!=null){
stack.push(cur);
cur=cur.left;
}
TreeNode top=stack.pop();
ret.add(top.val);
cur=top.right;
}
return ret;
}
// Subsequent traversal
public List<Integer> postorderTraversal(TreeNode root) {
Stack<TreeNode> stack=new Stack<>();
List<Integer> ret=new ArrayList<>();
TreeNode cur=root;
TreeNode prev=null;
while(cur!=null || !stack.isEmpty()){
while(cur!=null){
stack.push(cur);
cur=cur.left;
}
TreeNode top=stack.peek();
// When the top element of the stack is traversed or printed eject
if(top.right==null || top.right==prev){
stack.pop();
ret.add(top.val);
prev=top;// Record the most recently printed nodes
}else{
cur=top.right;
}
}
return ret;
}
The completeness test of binary tree
public boolean isCompleteTree(TreeNode root) {
if(root==null) return true;
Queue<TreeNode> queue=new LinkedList<>();
queue.offer(root);
boolean flg=false;
while(!queue.isEmpty()){
TreeNode tmp=queue.poll();
if(flg){
if(tmp.left!=null || tmp.right!=null){
return false;
}
}
if(tmp.left!=null && tmp.right!=null){
// Both the left and right children have
queue.offer(tmp.left);
queue.offer(tmp.right);
}else if(tmp.right!=null){
// Only the right child
return false;
}else if(tmp.left!=null){
// Only the left child
queue.offer(tmp.left);
flg=true;
}else{
// There are no children left or right
flg=true;;
}
}
return true;
}
Summary
That's what we have today , If you have any questions, you can leave a message in the comment area 
边栏推荐
- BEAUTIFUL GGPLOT VENN DIAGRAM WITH R
- Jenkins voucher management
- [C language] Yang Hui triangle, customize the number of lines of the triangle
- Differences between nodes and sharding in ES cluster
- 深入理解PyTorch中的nn.Embedding
- Repeat, tile and repeat in pytorch_ The difference between interleave
- YYGH-BUG-04
- Applet link generation
- Filtre de profondeur de la série svo2
- HOW TO CREATE AN INTERACTIVE CORRELATION MATRIX HEATMAP IN R
猜你喜欢
Mish shake the new successor of the deep learning relu activation function
YYGH-BUG-05
Jenkins voucher management
From scratch, develop a web office suite (3): mouse events
Dynamic debugging of multi file program x32dbg
GGPUBR: HOW TO ADD ADJUSTED P-VALUES TO A MULTI-PANEL GGPLOT
PyTorch nn. Full analysis of RNN parameters
自然语言处理系列（一）——RNN基础
Experiment of connecting mobile phone hotspot based on Arduino and esp8266 (successful)
Deep understanding of NN in pytorch Embedding
随机推荐
Analyse de l'industrie
二分刷题记录（洛谷题单）区间的甄别
Uniapp uni list item @click, uniapp uni list item jump with parameters
PHP 2D and multidimensional arrays are out of order, PHP_ PHP scrambles a simple example of a two-dimensional array and a multi-dimensional array. The shuffle function in PHP can only scramble one-dim
Full link voltage measurement
Yygh-9-make an appointment to place an order
Leetcode209 长度最小的子数组
SVO2系列之深度濾波DepthFilter
CDA数据分析——AARRR增长模型的介绍、使用
Log4j2
Deep understanding of P-R curve, ROC and AUC
FastDateFormat为什么线程安全
YYGH-9-预约下单
Fresh, 2022 advanced Android interview must know 100 questions (interview questions + answer analysis)
【C语言】十进制数转换成二进制数
Filtre de profondeur de la série svo2
Codeforces 771 div2 B (no one FST, refers to himself)
字符串回文hash 模板题 O(1)判字符串是否回文
Log4j2
Experiment of connecting mobile phone hotspot based on Arduino and esp8266 (successful)