二叉树和递归

曾经终败给现在 2023-07-04 12:42 61阅读 0赞

## 二叉树和递归 ##

### 文章目录 ###

*   *  二叉树和递归
     *   *  1.二叉树的最大深度
         *  2.二叉树的最小深度
         *  3.反转二叉树
         *  4.相同的树
         *  5.完全二叉树的节点个数
         *  6.平衡二叉树判断
         *  7.路径总和
         *  8.路径总和II
         *  9.路径总和III
         *  10.求根到叶节点数字之和
         *  11.二叉搜索树最近公共祖先
         *  12.二叉树的最近公共祖先
         *  13.二叉搜索树中第k小元素
         *  14.删除二叉搜索树中的节点
         *  15.将有序数组转为二叉搜索树

### 1.二叉树的最大深度 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70]

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

### 2.二叉树的最小深度 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 1]

/**
         * 以root节点为根的二叉树的最小深度 = min(以root.left为根的二叉树的最小深度，以root.right为根的二叉树的最小深度) + 1（root节点）
         * @param root
         * @return
         */
        public int minDepth(TreeNode root) {
        
            if(root == null){
        
                return 0;
            }else if(root.left != null && root.right != null){
        
                return Math.min(minDepth(root.left),minDepth(root.right)) + 1;
            }else if(root.left != null){
        
                return minDepth(root.left) + 1;
            }else{
        
                return minDepth(root.right) + 1;
            }
        }

### 3.反转二叉树 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 2]

public TreeNode invertTree(TreeNode root) {
        
            if(root == null)
                return null;
            invertTree(root.left);
            invertTree(root.right);
            TreeNode tmpLeft = root.left;
            TreeNode tmpRight = root.right;
            root.right = tmpLeft;
            root.left = tmpRight;
            return root;
        }

### 4.相同的树 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 3]

public boolean isSameTree(TreeNode p, TreeNode q) {
        
            if(p == null && q == null)
                return true;
            if(p == null && q != null)
                return false;
            if(p != null && q == null)
                return false;
            if(p.val != q.val)
                return false;
            return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
        }

### 5.完全二叉树的节点个数 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 4]

/**
         * 二叉树节点数 = 左子树节点数 + 右子树节点数 + 当前节点
         * @param root
         * @return
         */
        public int countNodes(TreeNode root) {
        
            if(root == null)
                return 0;
            return countNodes(root.left) + countNodes(root.right) + 1;
        }

### 6.平衡二叉树判断 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 5]

public boolean isBalanced(TreeNode root) {
        
            if(root == null)
                return true;
            if(Math.abs(getHeight(root.left) - getHeight(root.right)) > 1)
                return false;
            else
                return isBalanced(root.left) && isBalanced(root.right);
        }
    
        public int getHeight(TreeNode root) {
        
            if (root == null) {
        
                return 0;
            } else {
        
                int lh = getHeight(root.left);
                int rh = getHeight(root.right);
                return Math.max(lh, rh) + 1;
            }
        }

### 7.路径总和 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 6]

public boolean hasPathSum(TreeNode root, int sum) {
        
            if(root == null)
                return false;
            if(root.left == null && root.right == null)
                return root.val == sum;
            if(hasPathSum(root.left,sum - root.val)){
        
                return true;
            }
            if(hasPathSum(root.right,sum - root.val)){
        
                return true;
            }
            return false;
        }

### 8.路径总和II ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 7]

public List<List<Integer>> pathSum(TreeNode root, int sum) {
        
            List<List<Integer>> res = new ArrayList<>();
            if(root == null)
                return res;
            if(root.left == null && root.right == null && root.val == sum){
        
                List<Integer> tmp = new ArrayList<>();
                tmp.add(root.val);
                res.add(tmp);
                return res;
            }
            List<List<Integer>> leftList = pathSum(root.left,sum - root.val);
            List<List<Integer>> rightList = pathSum(root.right,sum - root.val);
            for(List<Integer> list : leftList){
        
                list.add(0,root.val);
                res.add(list);
            }
            for(List<Integer> list : rightList){
        
                list.add(0,root.val);
                res.add(list);
            }
            return res;
        }

### 9.路径总和III ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 8]

public int pathSum(TreeNode root, int sum) {
        
            if(root == null)
                return 0;
            int res = findPath(root,sum);
            res += pathSum(root.left,sum);
            res += pathSum(root.right,sum);
            return res;
        }
        
        public int findPath(TreeNode node,int sum){
        
            if(node == null)
                return 0;
            int res = 0;
            if(node.val == sum)
                res += 1;
            res += findPath(node.left,sum - node.val);
            res += findPath(node.right,sum - node.val);
            return res;
        }

### 10.求根到叶节点数字之和 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 9]

int sum = 0;
        public int sumNumbers(TreeNode root) {
        
            sumNumbers(0,root);
            return sum;
        }
    
        private void sumNumbers(int i, TreeNode root) {
        
            if(root == null)
                return;
            int k = 10 * i + root.val;
            if(root.left == null && root.right == null)
                sum += k;
            sumNumbers(k,root.left);
            sumNumbers(k,root.right);
        }

### 11.二叉搜索树最近公共祖先 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 10]

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
            return lca(root, p, q);
        }
    
        public TreeNode lca(TreeNode root, TreeNode p, TreeNode q){
        
            if((root.val - p.val) * (root.val - q.val) <= 0){
        
                return root;
            }else if(root.val < p.val && root.val < q.val){
        
                return lca(root.right,p,q);
            }else{
        
                return lca(root.left,p,q);
            }
        }

### 12.二叉树的最近公共祖先 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 11]

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
            if(root == null)
                return null;
            if(root == q || root == p)
                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)
                return left;
            else
                return right;
        }

### 13.二叉搜索树中第k小元素 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 12]

List<Integer> res = new ArrayList<>();
        public int kthSmallest(TreeNode root, int k) {
        
            dfs(root,res);
            Collections.sort(res);
            return res.get(k-1);
        }
        public void dfs(TreeNode root,List<Integer> list){
        
            if(root == null){
        
                return;
            }
            dfs(root.left,list);
            list.add(root.val);
            dfs(root.right,list);
        }

### 14.删除二叉搜索树中的节点 ###

public TreeNode deleteNode(TreeNode root, int key) {
        
            if (root == null) {
        
                return null;
            }
            if (key < root.val) {
        
                // 待删除节点在左子树中
                root.left = deleteNode(root.left, key);
                return root;
            } else if (key > root.val) {
        
                // 待删除节点在右子树中
                root.right = deleteNode(root.right, key);
                return root;
            } else {
        
                // key == root.val，root 为待删除节点
                if (root.left == null) {
        
                    // 返回右子树作为新的根
                    return root.right;
                } else if (root.right == null) {
        
                    // 返回左子树作为新的根
                    return root.left;
                } else {
        
                    // 左右子树都存在，返回后继节点（右子树最左叶子）作为新的根
                    TreeNode successor = min(root.right);
                    successor.right = deleteMin(root.right);
                    successor.left = root.left;
                    return successor;
                }
            }
        }
    
        private TreeNode min(TreeNode node) {
        
            if (node.left == null) {
        
                return node;
            }
            return min(node.left);
        }
    
        private TreeNode deleteMin(TreeNode node) {
        
            if (node.left == null) {
        
                return node.right;
            }
            node.left = deleteMin(node.left);
            return node;
        }

### 15.将有序数组转为二叉搜索树 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 13]

public TreeNode sortedArrayToBST(int[] nums) {
        
            if(nums==null)
                return null;
            return bst(nums,0,nums.length-1);
        }
        public TreeNode bst(int[] nums,int left,int right) {
        
            if(left>right)
                return null;
            int mid = left + ((right-left)>>1);
            TreeNode root = new TreeNode(nums[mid]);
            root.left = bst(nums,left,mid-1);
            root.right = bst(nums,mid+1,right);
            return root;
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200210224136887.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200210224305913.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200210225506999.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200210230116994.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/2020021023020027.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200210232725466.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200210232811637.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200210234224380.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200210234458441.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20200210235256534.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/20200210235334114.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 11]: https://img-blog.csdnimg.cn/20200211000055866.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 12]: https://img-blog.csdnimg.cn/20200211000151709.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 13]: https://img-blog.csdnimg.cn/20200211001105908.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70