精华内容
下载资源
问答
  • 二叉树深度 虽然前面已经做了二叉树深度,仍然不牢固。 剑指offer里面用的是递归的方法。只要的思路就是,左子树和右子树的比较,大的一支加1作为深度。并不是此时右子树的深度就不加一,现在考虑的是该节点的...

    二叉树的深度

    虽然前面已经做了二叉树的深度,仍然不牢固。
    剑指offer里面用的是递归的方法。只要的思路就是,左子树和右子树的比较,大的一支加1作为深度。并不是此时右子树的深度就不加一,现在考虑的是该节点的深度,而不是左右子树的,左右子树只是helper。该节点可能也是其他结点的左右结点之一。
    借鉴的一个大神的图,很清晰:
    在这里插入图片描述
    也是相当于后序遍历。

    def depth(root, num):
        if not root:
            return num
        res1 = depth(root.left, num+1)
        res2 = depth(root.right, num+1)
        if res1 > res2:
            return res1
        else:
            return res2
    
    def maxdepth(root):
    	if not root:
    		return 0
    	depthleft = maxdepth(root.left)
    	depthright = maxdepth(root.right)
    	if depthleft > depthright:
    		depthleft += 1
    		return depthleft  # return的就是本结点的深度
    	else:
    		defpthright += 1
    		return depthright
    
    

    平衡二叉树

    如果直接套用maxdepth的函数的话,需要对每一个结点都调用一次这个函数,那么很多结点的深度都计算重复了。
    改进就是通过后序遍历,也是相当于上面maxdepth一样,记住了深度,依次比较。
    在自下而上求每个结点的深度的同时,附带判断一下左右子树的深度差是否大于1。直到判断到根节点,如果都是平衡二叉树,那么就是了。
    tips:多层的递归无法中途停止,借助类的self成员变量来保存中途的信息。

    class Solution(object):
        def isBalanced(self, root):  # 记录下每个结点的深度,后序遍历
            if not root:
                return True
            self.sign = True
            def maxdepth(root):
                if not root:
                    return 0
                nl = maxdepth(root.left)
                nr = maxdepth(root.right)
                if nl > nr :
                    if abs(nl-nr)>1:
                        self.sign = False
                    nl += 1
                    return nl
                else:
                    if abs(nl-nr)>1:
                        self.sign = False
                    nr += 1
                    return nr
    
            maxdepth(root)
            return self.sign
    
    
    展开全文
  • 二叉树的最大深度//平衡二叉树

    二叉树的最大深度

    int maxDepth(struct TreeNode* root){
    	//左右子树最大高度 + 根
    	int left, right;
    	if (root){
    		return (left = maxDepth(root->left) + 1) > (right = maxDepth(root->right) + 1) ?
    		left : right;
    	}
    	else{
    		return 0;
    	}
    }
    

    平衡二叉树

    bool _isBalanced(struct TreeNode* root, int* cur){
    	if (root == NULL){
    		//当前根节点的高度
    		*cur = 0;
    		return true;
    	}
    	//下一层能够访问本层的left right
    	int left = 0, right = 0;
    	if (_isBalanced(root->left, &left) &&
    		_isBalanced(root->right, &right) &&
    		abs(left - right) < 2){
    		//以当前节点为根的树的最大深度
    		*cur = left > right ? left + 1 : right + 1;
    		return true;
    	}
    	else{
    		return false;
    	}
    }
    bool isBalanced(struct TreeNode* root){
    	//根的左右子树, 左右子树的左右子树 是否平衡
    	int dep = 0;
    	return _isBalanced(root, &dep);
    }
    
    展开全文
  • 文章目录二叉树最大深度题目描述具体代码1.递归写法2.精简版的递归写法3. 二叉树最大深度 题目描述 输入一棵二叉树的根节点,求该树的深度。从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径,...


    二叉树的最大深度

    题目描述

    输入一棵二叉树的根节点,求该树的深度。从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度为树的深度。

    示例
    给定二叉树 [3,9,20,null,null,15,7]
    在这里插入图片描述
    返回它的最大深度 3 。

    具体代码

    1.递归写法

    代码如下(示例):

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        int getDepth(TreeNode* node){
            if (node == NULL) return 0;
            int leftdepth = getDepth(node -> left);
            int rightdepth = getDepth(node -> right);
            int depth = max(leftdepth,rightdepth) + 1;
            return depth;
        }
        int maxDepth(TreeNode* root) {
            return getDepth(root);
        }
    };
    

    2.精简版的递归写法

    代码如下(示例):

    class Solution {
    public:
        int maxDepth(TreeNode* root) {
            if (root == NULL) return 0;
            return 1 + max(maxDepth(root->left), maxDepth(root->right));
        }
    };
    

    3.利用层序遍历

    代码如下(示例):

    class Solution {
    public:
        int maxDepth(TreeNode* root) {
            queue<TreeNode*> que;
            if (root == NULL) return 0;
            if (root != NULL) que.push(root);
            int level = 0;
            while (que.empty() == false){
                int size = que.size();
                for (int i = 0; i < size; i++){
                    TreeNode* tem = que.front();
                    que.pop();
                    if (tem -> left != NULL) que.push(tem -> left);
                    if (tem -> right != NULL) que.push(tem -> right);
                }
                level++;
            }
            return level;
        }
    };
    

    平衡二叉树

    题目描述

    给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

    示例1
    在这里插入图片描述

    输入:root = [3,9,20,null,null,15,7]
    输出:true

    示例2
    在这里插入图片描述

    输入:root = [1,2,2,3,3,null,null,4,4]
    输出:false

    具体代码

    class Solution {
    public:
        int getheight(TreeNode* node){
            if (node == nullptr) return 1;
            int leftheight = getheight(node -> left);
            int rightheight = getheight(node -> right);
            int height = max(leftheight,rightheight) + 1;
            return height;
        }
    
        bool isBalanced(TreeNode* root) {
            if (root == nullptr) return true;
            else return abs(getheight(root -> left)-getheight(root -> right)) <= 1 && isBalanced(root -> left) && isBalanced(root -> right);
        }
    };
    

    展开全文
  • 104. 二叉树最大深度 题目 104. 二叉树最大深度 给定一个二叉树,找出其最大深度二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,...

    104. 二叉树的最大深度

    题目

    104. 二叉树的最大深度

    给定一个二叉树,找出其最大深度。

    二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

    说明: 叶子节点是指没有子节点的节点。

    示例:
    给定二叉树 [3,9,20,null,null,15,7],
    3
    /
    9 20
    /
    15 7
    返回它的最大深度 3 。

    解法

    方法一:深度优先搜索

    如果我们知道了左子树和右子树的最大深度 l 和 r,那么该二叉树的最大深度即为
    max(l,r)+1

    而左子树和右子树的最大深度又可以以同样的方式进行计算。因此我们可以用「深度优先搜索」的方法来计算二叉树的最大深度。具体而言,在计算当前二叉树的最大深度时,可以先递归计算出其左子树和右子树的最大深度,然后在 O(1)时间内计算出当前二叉树的最大深度。递归在访问到空节点时退出。
    在这里插入图片描述

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

    方法二:广度优先搜索

    我们也可以用「广度优先搜索」的方法来解决这道题目,但我们需要对其进行一些修改,此时我们广度优先搜索的队列里存放的是「当前层的所有节点」。

    每次拓展下一层的时候,不同于广度优先搜索的每次只从队列里拿出一个节点,我们需要将队列里的所有节点都拿出来进行拓展,这样能保证每次拓展完的时候队列里存放的是当前层的所有节点,即我们是一层一层地进行拓展,最后我们用一个变量ans 来维护拓展的次数,该二叉树的最大深度即为ans。

    public int maxDepth(TreeNode root) {
            if (root == null) {
                return 0;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            int ans = 0;
            while (!queue.isEmpty()) {
                int size = queue.size();
                // 把这一层的都依次取出
                while (size-- > 0) {
                    TreeNode node = queue.remove();
                    if (node.left != null) {
                        queue.add(node.left);
                    }
                    if (node.right != null) {
                        queue.add(node.right);
                    }
                }
                ans++;
            }
            return ans;
        }
    

    111. 二叉树的最小深度

    题目

    111. 二叉树的最小深度

    给定一个二叉树,找出其最小深度。

    最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

    说明:叶子节点是指没有子节点的节点。
    在这里插入图片描述
    输入:root = [3,9,20,null,null,15,7]
    输出:2
    示例 2:

    输入:root = [2,null,3,null,4,null,5,null,6]
    输出:5

    解法

    深度优先搜索

    叶子节点的定义是左孩子和右孩子都为 null 时叫做叶子节点
    当 root 节点左右孩子都为空时,返回 1
    当 root 节点左右孩子有一个为空时,返回不为空的孩子节点的深度
    当 root 节点左右孩子都不为空时,返回左右孩子较小深度的节点值

    public int minDepth(TreeNode root) {
            if(root == null) return 0;
            //这道题递归条件里分为三种情况
            //1.左孩子和有孩子都为空的情况,说明到达了叶子节点,直接返回1即可
            if(root.left == null && root.right == null) return 1;
            //2.如果左孩子和由孩子其中一个为空,那么需要返回比较大的那个孩子的深度        
            int m1 = minDepth(root.left);
            int m2 = minDepth(root.right);
            //这里其中一个节点为空,说明m1和m2有一个必然为0,所以可以返回m1 + m2 + 1;
            if(root.left == null || root.right == null) return m1 + m2 + 1;
            
            //3.最后一种情况,也就是左右孩子都不为空,返回最小深度+1即可
            return Math.min(m1,m2) + 1; 
        }
    

    广度优先搜索

    同样,我们可以想到使用广度优先搜索的方法,遍历整棵树。

    当我们找到一个叶子节点时,直接返回这个叶子节点的深度。广度优先搜索的性质保证了最先搜索到的叶子节点的深度一定最小。

    public class Solution {
    
        class QueueNode {
            TreeNode node;
            int depth;
            public QueueNode(TreeNode node, int depth) {
                this.node = node;
                this.depth = depth;
            }
        }
    
        public int minDepth(TreeNode root) {
            if (root == null) {
                return 0;
            }
            Queue<QueueNode> queue = new LinkedList<>();
            queue.add(new QueueNode(root, 1));
            while (!queue.isEmpty()) {
                QueueNode nodeDepth = queue.remove();
                TreeNode node = nodeDepth.node;
                int depth = nodeDepth.depth;
                if (node.left == null && node.right == null) {
                    return depth;
                }
                if (node.left != null) {
                    queue.add(new QueueNode(node.left, depth + 1));
                }
                if (node.right != null) {
                    queue.add(new QueueNode(node.right, depth + 1));
                }
            }
            return 0;
        }
    }
    

    559. N 叉树的最大深度

    题目

    559. N 叉树的最大深度

    给定一个 N 叉树,找到其最大深度。

    最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

    N 叉树输入按层序遍历序列化表示,每组子节点由空值分隔(请参见示例)

    在这里插入图片描述
    输入:root = [1,null,3,2,4,null,5,6]
    输出:3

    解答

    深度优先搜索

    解决这个问题的最直观方法就是递归。
    递归去求每个子节点的最大深度,返回其中最大的子树深度+1
    不同的是,二叉树中求的是左子树和右子树的最大值。

    public int maxDepth(Node root) {
            if (root == null) {
                return 0;
            }
            // 如果没有子树 则为1
            if (root.children.isEmpty()) {
                return 1;
            }
            // 递归去求每个子节点的最大深度
            List<Integer> heights = new ArrayList<>();
            for (Node item : root.children) {
                heights.add(maxDepth(item));
            }
            // 返回其中最大的深度+1
            return Collections.max(heights) + 1;
        }
    

    迭代

    我们也可以用「广度优先搜索」的方法来解决这道题目,但我们需要对其进行一些修改,此时我们广度优先搜索的队列里存放的是「当前层的所有节点」。

    每次拓展下一层的时候,不同于广度优先搜索的每次只从队列里拿出一个节点,我们需要将队列里的所有节点都拿出来进行拓展,这样能保证每次拓展完的时候队列里存放的是当前层的所有节点,即我们是一层一层地进行拓展,最后我们用一个变量ans 来维护拓展的次数,该二叉树的最大深度即为ans。

    public int maxDepth(Node root) {
        if (root == null) {
            return 0;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        int depth = 0;
        while (!queue.isEmpty()) {
            int n = queue.size();
            depth++;
            // 每一层的所有节点都遍历一遍
            while (n-- != 0) {
            	// 所有子节点都入队
                for (Node item : queue.remove().children) {
                    queue.add(item);
                }
            }
        }
        return depth;
    }
    

    110. 平衡二叉树

    题目

    110. 平衡二叉树

    给定一个二叉树,判断它是否是高度平衡的二叉树。

    本题中,一棵高度平衡二叉树定义为:

    一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
    在这里插入图片描述
    输入:root = [1,2,2,3,3,null,null,4,4]
    输出:false

    解法

    从底至顶(提前阻断)

    此方法为本题的最优解法,但“从底至顶”的思路不易第一时间想到。

    思路是对二叉树做先序遍历,从底至顶返回子树最大高度,若判定某子树不是平衡树则 “剪枝” ,直接向上返回。

    算法流程:

    recur(root):

    • 递归返回值:

      • 当节点root 左 / 右子树的高度差 < 2:则返回以节点root为根节点的子树的最大高度,即节点 root 的左右子树中最大高度加 1( max(left, right) + 1 );
      • 当节点root 左 / 右子树的高度差 ≥2 :则返回 −1 ,代表 此子树不是平衡树 。
    • 递归终止条件:

      • 当越过叶子节点时,返回高度 0 ;
      • 当左(右)子树高度 left== -1 时,代表此子树的 左(右)子树 不是平衡树,因此直接返回 -1 ;
    	public boolean isBalanced(TreeNode root) {
            return recur(root) != -1;
        }
    
        public int recur(TreeNode root) {
        	// 叶子节点高度为0
            if (root == null) {
                return 0;
            }
            // 如果不平衡则直接返回
            int leftHeight = recur(root.left);
            if (leftHeight == -1) {
                return -1;
            }
            int rightHeight = recur(root.right);
            if (rightHeight == -1) {
                return -1;
            }
            // 判断是否高度相差在2以内
            return Math.abs(leftHeight - rightHeight) < 2 ? Math.max(leftHeight, rightHeight) + 1 : -1;
        }
    

    从顶至底(暴力法)

    此方法容易想到,但会产生大量重复计算,时间复杂度较高。

    思路是构造一个获取当前节点最大深度的方法 depth(root) ,通过比较此子树的左右子树的最大高度差abs(depth(root.left) - depth(root.right)),来判断此子树是否是二叉平衡树。若树的所有子树都平衡时,此树才平衡。

    class Solution {
        public boolean isBalanced(TreeNode root) {
            if (root == null) return true;
            return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }
    
        private int depth(TreeNode root) {
            if (root == null) return 0;
            return Math.max(depth(root.left), depth(root.right)) + 1;
        }
    }
    
    展开全文
  • 104. 二叉树最大深度 给定一个二叉树,找出其最大深度二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,20,null,null,15,7], 3 / \...
  • 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。 给定二叉树[3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7 返回true。示例 2: 给定二叉树[1,2,2,3,3,n...
  • 一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。 示例1: 输入:root = [3,9,20,null,null,15,7] 输出:true 示例2: 输入:root = [1,2,2,3,3,null,null,4,4] 输出:...
  • 平衡二叉树深度、递归) https://leetcode-cn.com/problems/balanced-binary-tree/ 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点的左右两个子树...
  • 104. 二叉树的最大深度 110. 平衡二叉树 104. 二叉树的最大深度 【题目】: 【代码】: 效果: 110. 平衡二叉树 【题目】: 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡...
  • 平衡二叉树 题解 二叉树的深度(后序遍历、层序遍历,清晰图解) 平衡二叉树(从底至顶、从顶至底,清晰图解) 思路 二叉树的深度 平衡二叉树 代码 二叉树的深度 # Definition for a binary tree ...
  • 二叉树最大深度

    2019-05-22 09:47:00
    文章目录一、 二叉树结构体一、求最大深度 一、 二叉树结构体 /*** * 二叉树基本的方法 */ public class TreeNode { private String val; private TreeNode left; private TreeNode right; TreeNode...
  • 104. 二叉树最大深度 给定一个二叉树,找出其最大深度二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,20,null,null,15,7] 3 ...
  • 二叉树的深度以及判断平衡二叉树

    千次阅读 2016-05-23 23:14:15
    输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度--一个根节点的左右有几个子节点,而该树的深度就是求左右子节点的最大一个+1public int...
  • 55题二叉树的深度、55题平衡二叉树
  • 平衡二叉树的定义:要求每个结点的左右差为0或者-1或者1; 方法:嵌套法 树空时,n0=0; 第一层n1=1; 公式:N_h=N_h-1+N_h-2+1; 第二层n2=1+0+1=2; 第三层n3=2+1+1=4; 第四层n4=4+2+1=7; 第五层n5=7+4+1=12; 因此,...
  • 104. 二叉树最大深度 给定一个二叉树,找出其最大深度二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 思路 直接DFS,返回左右子树深度大的即可。 代码 /** ...
  • 二叉树最大深度 给定一个二叉树,找出其最大深度二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,20,null,null,15,7] 3 / \ 9 ...
  • 如果某二叉树中任意结点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。 输入:二叉树[5,7,11,null,null,12,9,null,null,null,null]如下所示, 5 / \ 7 11 / \ 12 9 输出:true    思路:二叉树...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 19,140
精华内容 7,656
关键字:

平衡二叉树的最大深度