脚本宝典收集整理的这篇文章主要介绍了

树的总结–树的性质(树的深度) leetcode

脚本宝典小编觉得挺不错的,现在分享给大家,也给大家做个参考,希望能帮助你少写一行代码,多一份安全和惬意。

Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from
the root node down to the nearest leaf node.

递归解法

说明

如果一个node的左儿子为空 右儿子不空 从root 到左儿子的路径不算是minimum deepth因为左儿子不算这个node的leaf node所以要比最大深度那道题要多一个判断:
如果左儿子空返回右儿子的deepth 右儿子空返回左儿子deepth

复杂度

时间O(n)空间栈O(logn)

代码

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

广度优先搜索

说明

用BFS方法, 遇到第一个子叶都为空得节点返回当前深度

复杂度

时间O(n), 空间时间O(n)

代码

  public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int res = 0;
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left == null && node.right == null) {
                    return res + 1;//node已经算入了 所以要+1 
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            res += 1;
        }
        return res;
    }

Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from
the root node down to the farthest leaf node.

递归解法

说明

递归条件是,它的最大深度是它左子树的最大深度和右子树最大深度中较大的那个加1.返回条件是遇到null节点返回0.

复杂度

时间O(n)空间栈O(logn)

代码

public class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null){
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left, right) + 1//深度=子数深度+1;
    }

广度优先搜索

说明

用BFS方法, 直到遍历完整个树返回最长深度

复杂度

时间O(n), 空间O(n)

代码

public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int res = 0;
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            res += 1;
        }
        return res;
    }

Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary
tree in which the depth of the two subtrees of every node never differ
by more than 1.

递归

说明

还是求树的深度问题, 但是当左子树和右子树不平衡的时候要向上返回-1, 这样如果最后结果为-1则有不平衡的子树

复杂度

时间O(n), 空间栈O(logn)

代码

public boolean isBalanced(TreeNode root) {
    return checkBalance(root) != -1;
}
public int checkBalance(TreeNode root){
    if (root == null){
        return 0;
    }
    int left = checkBalance(root.left);
    int right = checkBalance(root.right);
    if (left == -1|| right == -1|| Math.abs(left - right) > 1){
        return -1;
    }//如果left或者right不平衡就网上返回-1;
    return Math.max(left, right) + 1;
}
  

总结

以上是脚本宝典为你收集整理的

树的总结–树的性质(树的深度) leetcode

全部内容,希望文章能够帮你解决

树的总结–树的性质(树的深度) leetcode

所遇到的程序开发问题,欢迎加入QQ群277859234一起讨论学习。如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典网站推荐给程序员好友。 本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。

80%的人都看过