当前位置:   article > 正文

leetcode刷题-二叉树03

leetcode刷题-二叉树03

代码随想录二叉树part03|104.二叉树的最大深度、111.二叉树的最小深度、222.完全二叉树的节点个数

104.二叉树的最大深度

代码随想录文档讲解
LeetCode

本题在前一章节层序遍历时已完成。(迭代法:层序遍历)
(↓递归法:后序遍历)
首先明确二叉树的深度和高度:
深度为到根节点的距离,如节点20,深度为2;节点7,深度为3(从1开始算深度)
高度为到叶子节点的距离,如节点7,高度为1,节点20,高度为2,节点3,高度3

  	3
   /   \
  9		20
  		/	\
  	  15	 7
  • 1
  • 2
  • 3
  • 4
  • 5

如何遍历呢?
高度:后序遍历(左右根),从下往上计数
深度:前序遍历(根左右),从上往下计数

二叉树的最大深度:根节点的高度

伪代码c++

int getheight(node){
	if(node==NULL) return 0;
	int leftheight = getheight(node->left);
	int rightheight = getheight(node->right);
	int height = 1+max(leftheight, rightheight);
	return height;
// 上述if后面的代码可以合并为一行
// return 1+max(getheight(node->left), getheight(node->right));
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

python代码

# 方法一
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from collections import deque
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root: return 0
        leftheight = self.maxDepth(root.left)
        rightheight = self.maxDepth(root.right)
        return 1 + max(leftheight, rightheight)

# 方法二:之前的实现—层序遍历
from collections import deque
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        result = 0
        queue = deque([root])
        while queue:
            size = len(queue)
            result += 1
            while size:
                size -= 1
                cur = queue.popleft()
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
        return result
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34

111.二叉树的最小深度

leetcode题目链接
代码随想录文档讲解

最小深度:根节点到最近叶子节点的深度

思路

遍历顺序三种都可以:

  1. 前序遍历求深度(根左右)
  2. 迭代法,层序遍历
  3. 但后序遍历代码更简洁,伪代码使用后序遍历

后序遍历:将孩子节点的情况返回给根节点,根节点记录

本题可能存在的陷阱(见代码)
在这里插入图片描述

伪代码(C++)

int getheight(node){
	if(node==NULL) return 0;
	int leftheight = getheight(node->left);
	int rightheight = getheight(node->right);
	// 有陷阱 如果节点左子树为空,但右子树不为空,会出现错误情况
	if(node->left == NULL && node->right != NULL){
		return 1 + rightheight;
	}
	if(node->left != NULL && node->right == NULL){
		return 1 + leftheight;
	}
	int result = 1 + min(leftheight, rightheight);
	return result;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

python代码

# 后序遍历
from collections import deque
class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        leftheight = self.minDepth(root.left)
        rightheight = self.minDepth(root.right)

        if root.left and not root.right:
            return 1 + leftheight
        if not root.left and root.right:
            return 1 + rightheight
        result = 1 + min(leftheight, rightheight)
        return result
        
# 层序遍历
from collections import deque
class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        res = 1
        q = deque([root])
        while q:
            size = len(q)
            while size:
                cur = q.popleft()
                if cur.left:
                    q.append(cur.left)
                if cur.right:
                    q.append(cur.right)
                if not cur.left and not cur.right:
                    return res
                size -= 1
            res += 1
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36

222.完全二叉树的节点个数

leetcode题目链接
代码随想录文档讲解

思路

如果当成普通二叉树,前中后序都可以求得二叉树的节点个数,层序遍历的迭代法也可以。

伪代码(C++)

int getNum(node){
	if(node==NULL) return 0;
	leftnum = getNum(node->left);        //左
	rightnum =  getNum(node->right);  //右
	result = 1 + leftnum + rightnum;      //中
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

若使用完全二叉树的特性:
除了底层节点,上面的节点都是满的,底层节点从左到右是满的。
满二叉树节点数量的计算公式: 2 n − 1 2^n-1 2n1
在这里插入图片描述
如何去判断子树是满二叉树呢?
如果是满二叉树的话 ,向左遍历的深度和向右遍历的深度是相等的。
如果不是满二叉树,继续向下遍历,子树可能是满二叉树。

子树如果为满二叉树可以根据公式计算节点数量,然后返回给根节点。

伪代码(C++)

本题的终止条件:

  1. 节点为空
  2. 子树为满二叉树
int getNum(node){
	if(node == NULL) return 0;
	left = node->left;
	right = node->right;
	leftdeepth = 0;
	rightdepth = 0;
	while(left)[
		left = left->left;
		leftdepth++;
	}
	while(right){
		right = right->right;
		rightdepth++;
	}
	if(leftdepth == rightdeepth) return 2<<leftdepth - 1; // 位运算 
	// 2 左移一位: 2<<1,相当于2的2次方:4

	leftnum = getNum(node->left);
	rightnum =  getNum(node->right);
	result = 1 + leftnum + rightnum;
	return result;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

python代码

# 普通二叉树
class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root: return 0
        return 1 + self.countNodes(root.left) + self.countNodes(root.right)
  
# 完全二叉树
class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root: return 0
        leftdepth = 0
        rightdepth = 0
        left = root.left
        right = root.right
        while left:
            leftdepth += 1
            left = left.left
        while right:
            rightdepth += 1
            right = right.right
        if leftdepth == rightdepth:
            return (2<<leftdepth) - 1
            # return 2 ** (leftdepth+1) - 1
        return 1 + self.countNodes(root.left) + self.countNodes(root.right)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/运维做开发/article/detail/818085
推荐阅读
相关标签
  

闽ICP备14008679号