判别一棵二叉树是否是一棵正则二叉树
时间: 2023-12-01 17:41:05 浏览: 47
判别一棵二叉树是否是一棵正则二叉树的方法如下:
1. 如果此数是空树,则一定是正则二叉树。
2. 如果不是空树,则从根节点开始比较其左右子树,如果左右子树相等,则是正则二叉树。
3. 递归终止条件是某个节点左右子树都为空或只有一个子树。
以下是判别一棵二叉树是否是一棵正则二叉树的Python代码实现:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def isNormalTree(root: TreeNode) -> bool:
if not root:
return True
if not root.left and not root.right:
return True
elif root.left and root.right:
return isNormalTree(root.left) and isNormalTree(root.right)
else:
return False
```
相关问题
习题:设二叉树按照二叉链表存储,编写算法判别一棵二叉树是否是一棵正则二叉树,正则二叉树是指在二叉树中不存在子树个数为1的结点。
以下是判断一棵二叉树是否为正则二叉树的Python算法:
```python
class TreeNode:
def __init__(self, val=None, left=None, right=None):
self.val = val
self.left = left
self.right = right
def is_regular_binary_tree(root):
if not root:
return True
if not root.left and not root.right:
return True
if root.left and root.right:
return is_regular_binary_tree(root.left) and is_regular_binary_tree(root.right)
return False
```
设二叉树按二叉链表存放,写算法判别一棵二叉树是否是一棵正则二叉树。正则二叉树是指在二叉树中不存在子树个数为1的结点。二叉树的前序和中序遍历序列,以此构造二叉树的链式存储,若该二叉树是一棵正则二叉树,则输出Yes,否则输出No
以下是算法实现:
1. 如果二叉树为空,返回Yes
2. 如果二叉树只有一个结点,返回Yes
3. 如果左子树为空,但右子树非空,返回No
4. 如果右子树为空,但左子树非空,返回No
5. 对左子树和右子树分别进行递归判断,如果均为正则二叉树,则返回Yes,否则返回No
代码如下:
```python
class Node:
def __init__(self, val=None):
self.val = val
self.left = None
self.right = None
def is_regular_binary_tree(preorder, inorder):
if not preorder or not inorder:
return True
if len(preorder) == 1 and len(inorder) == 1:
return True
if len(preorder) != len(inorder):
return False
root_val = preorder[0]
root_idx = inorder.index(root_val)
left_inorder = inorder[:root_idx]
right_inorder = inorder[root_idx+1:]
left_preorder = preorder[1:1+len(left_inorder)]
right_preorder = preorder[1+len(left_inorder):]
if not left_inorder and right_inorder:
return False
if not right_inorder and left_inorder:
return False
return is_regular_binary_tree(left_preorder, left_inorder) and is_regular_binary_tree(right_preorder, right_inorder)
preorder = [1,2,4,5,3,6,7]
inorder = [4,2,5,1,6,3,7]
root = Node(preorder[0])
root.left = Node(preorder[1])
root.right = Node(preorder[-1])
print("Yes" if is_regular_binary_tree(preorder, inorder) else "No")
```
输入的是前序和中序遍历序列,如果该二叉树是一棵正则二叉树,则输出Yes,否则输出No。