java算法-二叉树

「爱情、让人受尽委屈。」 2022-02-17 02:17 303阅读 0赞

### **1、求二叉树最大或最小深度** ###

public int maxDepth(Tree root){
            if(root == null)
                return 0;
            return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
        }
    
        public int minDepth(Tree root){
            if(root == null)
                return 0;
            return 1 + Math.min(maxDepth(root.left), maxDepth(root.right));
        }

### **2、反转一颗二叉树** ###

public Tree invertTree(Tree root){
            if(root == null){
                return null;
            }
            Tree left = invertTree(root.left);
            Tree right = invertTree(root.right);
            root.right = left;
            root.left = right;
            return root;
        }

**3、比较2颗二叉树是否一样**

public boolean compareTree(Tree root01,Tree root02){
            if(root01 == null && root02 == null){
                return true;
            }else if(root01 == null || root02 == null){
                return false;
            }
    
            boolean left = compareTree(root01.left,root02.left);
            if(!left){
                return false;
            }
            boolean right = compareTree(root01.right,root02.right);
            if(!right){
                return false;
            }
            return true;
        }

### **4、计算二叉树一共有多少个节点** ###

public int allTreeNode(Tree root){
            if(root == null){
                return 0;
            }
            if(root.left == null && root.right == null){
                return 1;
            }
            return allTreeNode(root.left) + allTreeNode(root.right);
        }

### **5、计算，树由子节点到根节点，是否存在一条路径 使他们的值是sum** ###

public boolean pathTree(Tree root,int sum){
            if(root == null){
                return false;
            }
            if(root.right == null && root.left == null){
                return sum == root.val;
            }
    
            sum -= root.val;
            if(sum < 0){
                return false;
            }
            return pathTree(root.right,sum) || pathTree(root.left,sum);
        }

### **6、求一颗二叉树，所有叶子节点的左节点的和** ###

public int leftSum(Tree root){
            if(root == null || (root.left == null && root.right == null)){
                return 0;
            }
    
            int leftVal = 0;
            if(root.left != null){
                leftVal = root.left.val;
            }
            return leftVal + leftSum(root.left) + leftSum(root.right);
        }

### **7、给一颗二叉树，返回所有，子节点到根节点的组合字符串** ###

public List<StringBuilder> binaryTree(Tree root){
            List<StringBuilder> returnStr = new LinkedList<>();
            if(root == null){
                return returnStr;
            }
            if(root.right ==null && root.left == null){
                returnStr.add(new StringBuilder(root.val + ""));
                return returnStr;
            }
            returnStr.addAll(binaryTree(root.left));
            returnStr.addAll(binaryTree(root.right));
    
            //添加当前数字
            for(StringBuilder str : returnStr){
                str.insert(0,root.val + "->");
            }
            return returnStr;
        }

### **8、给一颗二叉树和一个数字sum,找到所有根路径到叶子路径总和为sum的组合数量 。 开始点不一定在根节点，可以重任意子节点开始，但只能向下走** ###

public int pathSum3(Tree root,int sum){
            if(root == null){
                return 0;
            }
            return findPath(root,sum) + pathSum3(root.left,sum) + pathSum3(root.right,sum);
        }
    
        private int findPath(Tree node, int num){
            if(node == null){
                return 0;
            }
            if(node.right == null && node.left == null){
                if(node.val == num){
                    return 1;
                }
                return 0;
            }
            num -= node.val;
            if(num < 0){
                return 0;
            }
            return findPath(node.left,num) + findPath(node.right,num);
        }

### **9、给一颗二分搜索数（每一个节点的值，大于其左节点的值，小于其右节点的值）。 任意给2个节点，找到其最近的公共祖先点** ###

public Tree binarySearchTree(Tree tree,Tree note1,Tree note2){
            if(tree == null){
                return null;
            }
            if(note1.val < tree.val && note2.val < tree.val){
                return binarySearchTree(tree.left,note1,note2);
            }
            if(note1.val > tree.val && note2.val > tree.val){
                return binarySearchTree(tree.right,note1,note2);
            }
            return tree;
        }

### **10、验证该树是二分搜索树** ###

public boolean isBinarySearchTree(Tree tree){
            if(tree == null){
                return true;
            }
            if(tree.left != null && tree.left.val >= tree.val){
                return false;
            }
            if(tree.right != null && tree.right.val <= tree.val){
                return false;
            }
            return isBinarySearchTree(tree.left) && isBinarySearchTree(tree.right);
        }

### **11、将有序数组数组转换成一颗平衡的二分搜索树(左右节点高度之差的绝对值不超过1)** ###

public Tree paseBinarySearchTree(int[] array){
            int min = array[0];
            int max = array[array.length - 1];
            return binarySearchTree(array,min,max);
        }
    
        private Tree binarySearchTree(int[] array,int min,int max){
            if(min <= max){
                int mid  = (min + max) / 2;
                Tree left = binarySearchTree(array,min,mid -1);
                Tree right = binarySearchTree(array,mid + 1,max);
                Tree tree = new Tree(array[min]);
                tree.left = left;
                tree.right = right;
                return tree;
            }
            return null;
        }

### **12、在二分搜索树中找到第num小的树。左中右查找** ###

private int num;
        private Tree treeNode;
    
        public Tree getBinarySearchTree(Tree tree,int k){
            runBinarySearchTree(tree,k);
            return treeNode;
        }
    
    
        private void runBinarySearchTree(Tree tree,int k){
            if(tree == null || treeNode != null){
                return ;
            }
            getBinarySearchTree(tree.left,k);
            num ++;
            if(num == k){
                treeNode = tree;
            }
            getBinarySearchTree(tree.right,k);
        }

### **13、在一颗二叉树中，找到两个点的最近公共祖先** ###

private boolean note01;
        private boolean note02;
        private Tree commonTree;
    
        public void commonAncestor(Tree tree,Tree one,Tree two){
            if(tree == null){
                return ;
            }
            if(note01 && note02){
                return;
            }
            commonAncestor(tree.left,one,two);
            if(!note01 && tree == one){
                note01 = true;
            }
            if(!note02 && tree == two){
                note02 = true;
            }
            commonAncestor(tree.right,one,two);
            commonTree = tree;
        }