算法刷题——二叉树部分操作(翻转二叉树,平衡二叉树,最大深度)

 翻转二叉树

package 二叉树.反转二叉树;
 
import 二叉树.TreeNode;
 
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
 
public class Solution {
    public static void main(String[] args) {
        TreeNode root=new TreeNode(1);
        TreeNode node2=new TreeNode(2);
        TreeNode node3=new TreeNode(3);
        TreeNode node4=new TreeNode(4);
        TreeNode node5=new TreeNode(5);
        TreeNode node6=new TreeNode(6);
        TreeNode node7=new TreeNode(7);
        TreeNode node8=new TreeNode(8);
        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setRight(node6);
        node5.setLeft(node7);
        node5.setRight(node8);
        System.out.println(root);
        List integers=new ArrayList<>();
        inorderTraversal(root,integers);
        System.out.println(integers);
        List newRootIntegers=new ArrayList<>();
 
        TreeNode newRoot=invertTree(root);
        inorderTraversal(newRoot,newRootIntegers);
        System.out.println(newRootIntegers);
    }
    public static TreeNode invertTree(TreeNode root) {
        TreeNode node=null;
        if (root==null){
            return null;
        }
        invertTree(root.left);
        invertTree(root.right);
        node=root.right;
        root.right=root.left;
        root.left=node;
        return root;
    }
    public static void inorderTraversal(TreeNode root,List integers ){
        if (root==null){
            return;
        }
        inorderTraversal(root.left,integers);
        integers.add(root.val);
        inorderTraversal(root.right,integers);
    }
 
}

 二叉树最大深度

 力扣

package 二叉树.最大深度;
 
import 二叉树.TreeNode;
 
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
 
public class Solution {
    public static void main(String[] args) {
        TreeNode root=new TreeNode(1);
        TreeNode node2=new TreeNode(2);
        TreeNode node3=new TreeNode(3);
        TreeNode node4=new TreeNode(4);
        TreeNode node5=new TreeNode(5);
        TreeNode node6=new TreeNode(6);
        TreeNode node7=new TreeNode(7);
        TreeNode node8=new TreeNode(8);
        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setRight(node6);
        node5.setLeft(node7);
        node5.setRight(node8);
//        int max = maxDepth(root);
        int max = maxDepthMethodForLoop(root);
        System.out.println("----------二叉树最大深度为------"+max);
 
    }
    public static int maxDepth(TreeNode root) {
        int deep=0;
        if(root==null){
            return 0;
        }else{
            return Math.max( maxDepth(root.right), maxDepth(root.left))+1;
        }
    }
    public static int maxDepthMethodForLoop(TreeNode root) {
        int deep=0;
        Queue queue=new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size=queue.size();
 
            while (size>0){
                TreeNode treeNode=queue.poll();
                if(treeNode.left!=null){
                    queue.offer(treeNode.left);
                }
                if(treeNode.right!=null){
                    queue.offer(treeNode.right);
                }
                System.out.println(queue);
                System.out.println(queue.size());
                System.out.println(size);
 
                size--;
 
            }
 
            deep++;
        }
 
        return deep;
    }
 
}

平衡二叉树

力扣​​​​​​​

package 二叉树.平衡二叉树;
 
import 二叉树.TreeNode;
 
import java.util.ArrayList;
import java.util.List;
 
public class Solution {
    public static void main(String[] args) {
        TreeNode root=new TreeNode(1);
        TreeNode node2=new TreeNode(2);
        TreeNode node3=new TreeNode(3);
        TreeNode node4=new TreeNode(4);
        TreeNode node5=new TreeNode(5);
        TreeNode node6=new TreeNode(6);
        TreeNode node7=new TreeNode(7);
        TreeNode node8=new TreeNode(8);
        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setRight(node6);
        node5.setLeft(node7);
        node5.setRight(node8);
        int balanced = isBalanced(root);
        System.out.println(balanced);
    }
    public static int isBalanced(TreeNode root) {
        if(root==null){
            return 0;
        }
        int left=isBalanced(root.left);
        int right=isBalanced(root.right);
        System.out.println(left);
        System.out.println(right);
        if(left==-1||right==-1||Math.abs(left-right)>1){
            return -1;
        }
        return Math.max(left,right)+1;
 
    }
 
}