文章详情

登录

短信预约-IT技能 免费直播动态提醒

选择考试省份

  • 北京
  • 上海
  • 天津
  • 重庆
  • 河北
  • 山东
  • 辽宁
  • 黑龙江
  • 吉林
  • 甘肃
  • 青海
  • 河南
  • 江苏
  • 湖北
  • 湖南
  • 江西
  • 浙江
  • 广东
  • 云南
  • 福建
  • 海南
  • 山西
  • 四川
  • 陕西
  • 贵州
  • 安徽
  • 广西
  • 内蒙
  • 西藏
  • 新疆
  • 宁夏
  • 兵团

请输入下面的图形验证码

提交验证

短信预约提醒成功

二叉树节点的高度和深度，你区分开了么？

2024-12-03 00:14

关注

求高度还是求深度，你搞懂了不?

平衡二叉树题目地址：https://leetcode-cn.com/problems/balanced-binary-tree/

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

本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]


返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]


返回 false 。

题外话

咋眼一看这道题目和104.二叉树的最大深度很像，其实有很大区别。

这里强调一波概念：

但leetcode中强调的深度和高度很明显是按照节点来计算的，如图：


关于根节点的深度究竟是1 还是 0，不同的地方有不一样的标准，leetcode的题目中都是以节点为一度，即根节点深度是1。但维基百科上定义用边为一度，即根节点的深度是0，我们暂时以leetcode为准(毕竟要在这上面刷题)。

因为求深度可以从上到下去查 所以需要前序遍历(中左右)，而高度只能从下到上去查，所以只能后序遍历(左右中)

有的同学一定疑惑，为什么104.二叉树的最大深度中求的是二叉树的最大深度，也用的是后序遍历。

那是因为代码的逻辑其实是求的根节点的高度，而根节点的高度就是这颗树的最大深度，所以才可以使用后序遍历。

在104.二叉树的最大深度中，如果真正求取二叉树的最大深度，代码应该写成如下：(前序遍历)

  1. class Solution { 
  2. public: 
  3.     int result; 
  4.     void getDepth(TreeNode* node, int depth) { 
  5.         result = depth > result ? depth : result; // 中 
  6.  
  7.         if (node->left == NULL && node->right == NULL) return ; 
  8.  
  9.         if (node->left) { // 左 
  10.             depth++;    // 深度+1 
  11.             getDepth(node->left, depth); 
  12.             depth--;    // 回溯，深度-1 
  13.         } 
  14.         if (node->right) { // 右 
  15.             depth++;    // 深度+1 
  16.             getDepth(node->right, depth); 
  17.             depth--;    // 回溯，深度-1 
  18.         } 
  19.         return ; 
  20.     } 
  21.     int maxDepth(TreeNode* root) { 
  22.         result = 0; 
  23.         if (root == 0) return result; 
  24.         getDepth(root, 1); 
  25.         return result; 
  26.     } 
  27. }; 

可以看出使用了前序(中左右)的遍历顺序，这才是真正求深度的逻辑!

注意以上代码是为了把细节体现出来，简化一下代码如下：

  1. class Solution { 
  2. public: 
  3.     int result; 
  4.     void getDepth(TreeNode* node, int depth) { 
  5.         result = depth > result ? depth : result; // 中 
  6.         if (node->left == NULL && node->right == NULL) return ; 
  7.         if (node->left) { // 左 
  8.             getDepth(node->left, depth + 1); 
  9.         } 
  10.         if (node->right) { // 右 
  11.             getDepth(node->right, depth + 1); 
  12.         } 
  13.         return ; 
  14.     } 
  15.     int maxDepth(TreeNode* root) { 
  16.         result = 0; 
  17.         if (root == 0) return result; 
  18.         getDepth(root, 1); 
  19.         return result; 
  20.     } 
  21. }; 

本题思路

递归

此时大家应该明白了既然要求比较高度，必然是要后序遍历。

递归三步曲分析：

明确递归函数的参数和返回值

参数的话为传入的节点指针，就没有其他参数需要传递了，返回值要返回传入节点为根节点树的深度。

那么如何标记左右子树是否差值大于1呢。

如果当前传入节点为根节点的二叉树已经不是二叉平衡树了，还返回高度的话就没有意义了。

所以如果已经不是二叉平衡树了，可以返回-1 来标记已经不符合平衡树的规则了。

代码如下：

  1. // -1 表示已经不是平衡二叉树了，否则返回值是以该节点为根节点树的高度 
  2. int getDepth(TreeNode* node) 

明确终止条件

递归的过程中依然是遇到空节点了为终止，返回0，表示当前节点为根节点的树高度为0

代码如下：

  1. if (node == NULL) { 
  2.     return 0; 
  3. } 

明确单层递归的逻辑

如何判断当前传入节点为根节点的二叉树是否是平衡二叉树呢，当然是左子树高度和右子树高度相差。

分别求出左右子树的高度，然后如果差值小于等于1，则返回当前二叉树的高度，否则则返回-1，表示已经不是二叉树了。

代码如下：

  1. int leftDepth = depth(node->left); // 左 
  2. if (leftDepth == -1) return -1; 
  3. int rightDepth = depth(node->right); // 右 
  4. if (rightDepth == -1) return -1; 
  5.  
  6. int result; 
  7. if (abs(leftDepth - rightDepth) > 1) {  // 中 
  8.     result = -1; 
  9. } else { 
  10.     result = 1 + max(leftDepth, rightDepth); // 以当前节点为根节点的最大高度 
  11. } 
  12.  
  13. return result; 

代码精简之后如下：

  1. int leftDepth = getDepth(node->left); 
  2. if (leftDepth == -1) return -1; 
  3. int rightDepth = getDepth(node->right); 
  4. if (rightDepth == -1) return -1; 
  5. return abs(leftDepth - rightDepth) > 1 ? -1 : 1 + max(leftDepth, rightDepth); 

此时递归的函数就已经写出来了，这个递归的函数传入节点指针，返回以该节点为根节点的二叉树的高度，如果不是二叉平衡树，则返回-1。

getDepth整体代码如下：

  1. int getDepth(TreeNode* node) { 
  2.     if (node == NULL) { 
  3.         return 0; 
  4.     } 
  5.     int leftDepth = getDepth(node->left); 
  6.     if (leftDepth == -1) return -1; 
  7.     int rightDepth = getDepth(node->right); 
  8.     if (rightDepth == -1) return -1; 
  9.     return abs(leftDepth - rightDepth) > 1 ? -1 : 1 + max(leftDepth, rightDepth); 
  10. } 

最后本题整体递归代码如下：

  1. class Solution { 
  2. public: 
  3.     // 返回以该节点为根节点的二叉树的高度，如果不是二叉搜索树了则返回-1 
  4.     int getDepth(TreeNode* node) { 
  5.         if (node == NULL) { 
  6.             return 0; 
  7.         } 
  8.         int leftDepth = getDepth(node->left); 
  9.         if (leftDepth == -1) return -1; // 说明左子树已经不是二叉平衡树 
  10.         int rightDepth = getDepth(node->right); 
  11.         if (rightDepth == -1) return -1; // 说明右子树已经不是二叉平衡树 
  12.         return abs(leftDepth - rightDepth) > 1 ? -1 : 1 + max(leftDepth, rightDepth); 
  13.     } 
  14.     bool isBalanced(TreeNode* root) { 
  15.         return getDepth(root) == -1 ? false : true; 
  16.     } 
  17. }; 

迭代

在104.二叉树的最大深度中我们可以使用层序遍历来求深度，但是就不能直接用层序遍历来求高度了，这就体现出求高度和求深度的不同。

本题的迭代方式可以先定义一个函数，专门用来求高度。

这个函数通过栈模拟的后序遍历找每一个节点的高度(其实是通过求传入节点为根节点的最大深度来求的高度)

代码如下：

  1. // cur节点的最大深度，就是cur的高度 
  2. int getDepth(TreeNode* cur) { 
  3.     stack st; 
  4.     if (cur != NULL) st.push(cur); 
  5.     int depth = 0; // 记录深度 
  6.     int result = 0; 
  7.     while (!st.empty()) { 
  8.         TreeNode* node = st.top(); 
  9.         if (node != NULL) { 
  10.             st.pop(); 
  11.             st.push(node);                          // 中 
  12.             st.push(NULL); 
  13.             depth++; 
  14.             if (node->right) st.push(node->right);  // 右 
  15.             if (node->left) st.push(node->left);    // 左 
  16.  
  17.         } else { 
  18.             st.pop(); 
  19.             node = st.top(); 
  20.             st.pop(); 
  21.             depth--; 
  22.         } 
  23.         result = result > depth ? result : depth; 
  24.     } 
  25.     return result; 
  26. } 

然后再用栈来模拟前序遍历，遍历每一个节点的时候，再去判断左右孩子的高度是否符合，代码如下：

  1. bool isBalanced(TreeNode* root) { 
  2.     stack st; 
  3.     if (root == NULL) return true; 
  4.     st.push(root); 
  5.     while (!st.empty()) { 
  6.         TreeNode* node = st.top();                       // 中 
  7.         st.pop(); 
  8.         if (abs(getDepth(node->left) - getDepth(node->right)) > 1) { // 判断左右孩子高度是否符合 
  9.             return false; 
  10.         } 
  11.         if (node->right) st.push(node->right);           // 右（空节点不入栈） 
  12.         if (node->left) st.push(node->left);             // 左（空节点不入栈） 
  13.     } 
  14.     return true; 
  15. } 

整体代码如下：

  1. class Solution { 
  2. private: 
  3.     int getDepth(TreeNode* cur) { 
  4.         stack st; 
  5.         if (cur != NULL) st.push(cur); 
  6.         int depth = 0; // 记录深度 
  7.         int result = 0; 
  8.         while (!st.empty()) { 
  9.             TreeNode* node = st.top(); 
  10.             if (node != NULL) { 
  11.                 st.pop(); 
  12.                 st.push(node);                          // 中 
  13.                 st.push(NULL); 
  14.                 depth++; 
  15.                 if (node->right) st.push(node->right);  // 右 
  16.                 if (node->left) st.push(node->left);    // 左 
  17.  
  18.             } else { 
  19.                 st.pop(); 
  20.                 node = st.top(); 
  21.                 st.pop(); 
  22.                 depth--; 
  23.             } 
  24.             result = result > depth ? result : depth; 
  25.         } 
  26.         return result; 
  27.     } 
  28.  
  29. public: 
  30.     bool isBalanced(TreeNode* root) { 
  31.         stack st; 
  32.         if (root == NULL) return true; 
  33.         st.push(root); 
  34.         while (!st.empty()) { 
  35.             TreeNode* node = st.top();                       // 中 
  36.             st.pop(); 
  37.             if (abs(getDepth(node->left) - getDepth(node->right)) > 1) { 
  38.                 return false; 
  39.             } 
  40.             if (node->right) st.push(node->right);           // 右（空节点不入栈） 
  41.             if (node->left) st.push(node->left);             // 左（空节点不入栈） 
  42.         } 
  43.         return true; 
  44.     } 
  45. }; 

当然此题用迭代法，其实效率很低，因为没有很好的模拟回溯的过程，所以迭代法有很多重复的计算。

虽然理论上所有的递归都可以用迭代来实现，但是有的场景难度可能比较大。

例如：都知道回溯法其实就是递归，但是很少人用迭代的方式去实现回溯算法!

因为对于回溯算法已经是非常复杂的递归了，如果在用迭代的话，就是自己给自己找麻烦，效率也并不一定高。

总结

通过本题可以了解求二叉树深度 和 二叉树高度的差异，求深度适合用前序遍历，而求高度适合用后序遍历。

本题迭代法其实有点复杂，大家可以有一个思路，也不一定说非要写出来。

但是递归方式是一定要掌握的!

其他语言版本

Java

  1. class Solution { 
  2.     
  3.     public boolean isBalanced(TreeNode root) { 
  4.         return getHeight(root) != -1; 
  5.     } 
  6.  
  7.     private int getHeight(TreeNode root) { 
  8.         if (root == null) { 
  9.             return 0; 
  10.         } 
  11.         int leftHeight = getHeight(root.left); 
  12.         if (leftHeight == -1) { 
  13.             return -1; 
  14.         } 
  15.         int rightHeight = getHeight(root.right); 
  16.         if (rightHeight == -1) { 
  17.             return -1; 
  18.         } 
  19.         // 左右子树高度差大于1，return -1表示已经不是平衡树了 
  20.         if (Math.abs(leftHeight - rightHeight) > 1) { 
  21.             return -1; 
  22.         } 
  23.         return Math.max(leftHeight, rightHeight) + 1; 
  24.     } 
  25. } 
  26.  
  27. class Solution { 
  28.     
  29.     public boolean isBalanced(TreeNode root) { 
  30.         if (root == null) { 
  31.             return true; 
  32.         } 
  33.         Stack stack = new Stack<>(); 
  34.         TreeNode pre = null; 
  35.         while (root!= null || !stack.isEmpty()) { 
  36.             while (root != null) { 
  37.                 stack.push(root); 
  38.                 root = root.left; 
  39.             } 
  40.             TreeNode inNode = stack.peek(); 
  41.             // 右结点为null或已经遍历过 
  42.             if (inNode.right == null || inNode.right == pre) { 
  43.                 // 比较左右子树的高度差，输出 
  44.                 if (Math.abs(getHeight(inNode.left) - getHeight(inNode.right)) > 1) { 
  45.                     return false; 
  46.                 } 
  47.                 stack.pop(); 
  48.                 pre = inNode; 
  49.                 root = null;// 当前结点下，没有要遍历的结点了 
  50.             } else { 
  51.                 root = inNode.right;// 右结点还没遍历，遍历右结点 
  52.             } 
  53.         } 
  54.         return true; 
  55.     } 
  56.  
  57.      
  58.     public int getHeight(TreeNode root) { 
  59.         if (root == null) { 
  60.             return 0; 
  61.         } 
  62.         Deque deque = new LinkedList<>(); 
  63.         deque.offer(root); 
  64.         int depth = 0; 
  65.         while (!deque.isEmpty()) { 
  66.             int size = deque.size(); 
  67.             depth++; 
  68.             for (int i = 0; i < size; i++) { 
  69.                 TreeNode poll = deque.poll(); 
  70.                 if (poll.left != null) { 
  71.                     deque.offer(poll.left); 
  72.                 } 
  73.                 if (poll.right != null) { 
  74.                     deque.offer(poll.right); 
  75.                 } 
  76.             } 
  77.         } 
  78.         return depth; 
  79.     } 
  80. } 
  81.  
  82. class Solution { 
  83.     
  84.     public boolean isBalanced(TreeNode root) { 
  85.         if (root == null) { 
  86.             return true; 
  87.         } 
  88.         Stack stack = new Stack<>(); 
  89.         TreeNode pre = null; 
  90.         while (root != null || !stack.isEmpty()) { 
  91.             while (root != null) { 
  92.                 stack.push(root); 
  93.                 root = root.left; 
  94.             } 
  95.             TreeNode inNode = stack.peek(); 
  96.             // 右结点为null或已经遍历过 
  97.             if (inNode.right == null || inNode.right == pre) { 
  98.                 // 输出 
  99.                 if (Math.abs(getHeight(inNode.left) - getHeight(inNode.right)) > 1) { 
  100.                     return false; 
  101.                 } 
  102.                 stack.pop(); 
  103.                 pre = inNode; 
  104.                 root = null;// 当前结点下，没有要遍历的结点了 
  105.             } else { 
  106.                 root = inNode.right;// 右结点还没遍历，遍历右结点 
  107.             } 
  108.         } 
  109.         return true; 
  110.     } 
  111.  
  112.      
  113.     public int getHeight(TreeNode root) { 
  114.         if (root == null) { 
  115.             return 0; 
  116.         } 
  117.         int leftHeight = root.left != null ? root.left.val : 0; 
  118.         int rightHeight = root.right != null ? root.right.val : 0; 
  119.         int height = Math.max(leftHeight, rightHeight) + 1; 
  120.         root.val = height;// 用TreeNode.val来保存当前结点的高度 
  121.         return height; 
  122.     } 
  123. } 

Python

递归法：

  1. class Solution: 
  2.     def isBalanced(self, root: TreeNode) -> bool: 
  3.         return True if self.getDepth(root) != -1 else False 
  4.      
  5.     #返回以该节点为根节点的二叉树的高度，如果不是二叉搜索树了则返回-1 
  6.     def getDepth(self, node): 
  7.         if not node: 
  8.             return 0 
  9.         leftDepth = self.getDepth(node.left) 
  10.         if leftDepth == -1: return -1 #说明左子树已经不是二叉平衡树 
  11.         rightDepth = self.getDepth(node.right) 
  12.         if rightDepth == -1: return -1 #说明右子树已经不是二叉平衡树 
  13.         return -1 if abs(leftDepth - rightDepth)>1 else 1 + max(leftDepth, rightDepth) 

迭代法：

  1. class Solution: 
  2.     def isBalanced(self, root: TreeNode) -> bool: 
  3.         st = [] 
  4.         if not root: 
  5.             return True 
  6.         st.append(root) 
  7.         while st: 
  8.             node = st.pop() #中 
  9.             if abs(self.getDepth(node.left) - self.getDepth(node.right)) > 1: 
  10.                 return False 
  11.             if node.right: 
  12.                 st.append(node.right) #右（空节点不入栈） 
  13.             if node.left: 
  14.                 st.append(node.left) #左（空节点不入栈） 
  15.         return True 
  16.      
  17.     def getDepth(self, cur): 
  18.         st = [] 
  19.         if cur: 
  20.             st.append(cur) 
  21.         depth = 0 
  22.         result = 0 
  23.         while st: 
  24.             node = st.pop() 
  25.             if node: 
  26.                 st.append(node) #中 
  27.                 st.append(None) 
  28.                 depth += 1 
  29.                 if node.right: st.append(node.right) #右 
  30.                 if node.left: st.append(node.left) #左 
  31.             else: 
  32.                 node = st.pop() 
  33.                 depth -= 1 
  34.             result = max(result, depth) 
  35.         return result 

 

来源：代码随想录内容投诉

免责声明：

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题

  • 2024年上半年信息系统项目管理师第二批次真题及答案解析（完整版）

    难度     813人已做
    查看

  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看

  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看

  • 2024年上半年软考高项第一、二批次真题考点汇总（完整版）

    难度     435人已做
    查看

  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机

二叉树节点的高度和深度，你区分开了么？

后端开发二叉树数据结构2024-12-03
位置：首页-资讯-后端开发
咦！没有更多了？去看看其它编程学习网 内容吧
首页课程
资料下载问答资讯