Day26——二叉树专题

青旅半醒 2024-04-01 14:28 72阅读 0赞

#### 文章目录 ####

*   *   *   *  8.二叉树的最小深度
             *  9.完全二叉树的节点个数
             *  10.平衡二叉树
             *  1.递归法
             *  2.迭代法

--------------------

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

**思路：**

左子树为空，右子树不为空，最小深度就是右子树的深度+1；

左子树不为空，右子树为空，最小深度就是左子树的深度+1；

**代码实现：**

class Solution {
        public int minDepth(TreeNode root) {
            if(root==null){
                return 0;
            }
            int leftDepth = minDepth(root.left);
            int rightDepth = minDepth(root.right);
            if(root.left==null&&root.right!=null){
                return 1+rightDepth;
            }
            if(root.right==null&&root.left!=null){
                return 1+leftDepth;
            }
            return Math.min(leftDepth,rightDepth)+1;
        }
     }

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

**1.通用递归法**

class Solution {
        public int countNodes(TreeNode root) {
            if(root==null){
                return 0;
            }
            int leftNum = countNodes(root.left);
            int rightNum = countNodes(root.right);
            return leftNum+rightNum+1;
        }
    }

**2.迭代法**

class Solution {
        
        public int countNodes(TreeNode root) {
        
            if(root==null){
        
                return 0;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            int result = 0;
            while(!queue.isEmpty()){
        
                int size = queue.size();
                while(size-->0){
        
                    TreeNode cur = queue.poll();
                    result++;
                    if(cur.left!=null){
        
                        queue.offer(cur.left);
                    }
                    if(cur.right!=null){
        
                        queue.offer(cur.right);
                    }
                }
            }
            return result;
        }
    }

**3.针对完全二叉树的解法**

class Solution {
        
        /**
         * 针对完全二叉树的解法
         *
         * 满二叉树的结点数为：2^depth - 1
         */
        public int countNodes(TreeNode root) {
        
            if(root == null) {
        
                return 0;
            }
            int leftDepth = getDepth(root.left);
            int rightDepth = getDepth(root.right);
            if (leftDepth == rightDepth) {
        // 左子树是满二叉树
                // 2^leftDepth其实是 （2^leftDepth - 1） + 1 ，左子树 + 根结点
                return (1 << leftDepth) + countNodes(root.right);
            } else {
        // 右子树是满二叉树
                return (1 << rightDepth) + countNodes(root.left);
            }
        }
    
        private int getDepth(TreeNode root) {
        
            int depth = 0;
            while (root != null) {
        
                root = root.left;
                depth++;
            }
            return depth;
        }
    }

##### 10.平衡二叉树 #####

\*\*求高度：\*\*后序—自底向上

**求深度**：前序—自上向下

*  二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
 *  二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。

**补充：**

![image-20221103213521082][]

**思路：**

使用后序，分别求出左右子树高度差，来判断左右子树高度差的绝对值是否大于1，大于1的话就不是平衡二叉树。只有知道左右子树的高度，才能来判断是否为平衡二叉树，所以遍历顺序是左右中。选择后序遍历。

##### 1.递归法 #####

**代码实现：**

class Solution {
        
       /**
         * 递归法
         */
        public boolean isBalanced(TreeNode root) {
        
            return getHeight(root) != -1;
        }
    
        private int getHeight(TreeNode root) {
        
            if (root == null) {
        
                return 0;
            }
            int leftHeight = getHeight(root.left);
            if (leftHeight == -1) {
        
                return -1;
            }
            int rightHeight = getHeight(root.right);
            if (rightHeight == -1) {
        
                return -1;
            }
            // 左右子树高度差大于1，return -1表示已经不是平衡树了
            if (Math.abs(leftHeight - rightHeight) > 1) {
        
                return -1;
            }
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }

##### 2.迭代法 #####

**代码实现：**

class Solution {
        
       /**
         * 迭代法，效率较低，计算高度时会重复遍历
         * 时间复杂度：O(n^2)
         */
        public boolean isBalanced(TreeNode root) {
        
            if (root == null) {
        
                return true;
            }
            Stack<TreeNode> stack = new Stack<>();
            TreeNode pre = null;
            while (root!= null || !stack.isEmpty()) {
        
                while (root != null) {
        
                    stack.push(root);
                    root = root.left;
                }
                TreeNode inNode = stack.peek();
                // 右结点为null或已经遍历过
                if (inNode.right == null || inNode.right == pre) {
        
                    // 比较左右子树的高度差，输出
                    if (Math.abs(getHeight(inNode.left) - getHeight(inNode.right)) > 1) {
        
                        return false;
                    }
                    stack.pop();
                    pre = inNode;
                    root = null;// 当前结点下，没有要遍历的结点了
                } else {
        
                    root = inNode.right;// 右结点还没遍历，遍历右结点
                }
            }
            return true;
        }

[image-20221103213521082]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/9848279b3f3841da8b677698ca62ddf4.png