时间戳

首页 > 解决方案 > 没有节点与其子节点具有相同的颜色 - 递归

python - 没有节点与其子节点具有相同的颜色 - 递归

问题描述

给出binary tree2 种颜色(green,red)决定给定的树是否是Green-Red树。Green-Red树的条件之一是：Each node has different color than its children

def checkTree(node):
    if node is None:
        return
    //return checkTree(node.left) and checkTree(node.right) - not sure about this 
    if node has 1 child:
        if they are same color:
            return False
        return True
    if node has 2 child:
        if left children or right children has same color as node:
            return False
        return True

问题是我不知道如何在这里调用递归。

标签： pythonrecursiontree

解决方案

我可以填写您缺少的与递归有关的一些部分，但其他部分我将保留为您的原始伪代码作为练习。

def checkTree(node):
    if node has no children:  # pseudo code, FIXME
        return True   # Terminate the recursion here

    if node has 1 child:
        if they are same color:
            return False
        return checkTree(singleChild)  # you need code that will find the child, FIXME
    if node has 2 children:
        if left children or right children has same color as node:
            return False
        return checkTree(node.left) and checkTree(node.right)

这里的递归部分是：

  1. WherecheckTree(n)被调用，它沿着树的一条腿递归。
  2. finalreturn True终止递归。

另外，这两个return False语句是优化，当树明显不满足条件时避免整条腿。

推荐阅读