如何递归地遍历二叉树？

Question

我有一个无法解答的测验问题：

给定一棵表示(5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))的树，其中第一项是节点，第二项是左分支树，第三项是右分支树，找到最大的锯齿形（在树中改变方向的选项）。在

所以这棵树从5开始，从左到3或从右到10，从3到20（它不能向右，右边是None）。从10点开始，它可以向左走到1号，或者向右走到15号，等等

我失败了，因为我有问题，甚至递归地走一棵树。我无法决定如何选择向左或向右走，当第二次、第三次等在树上行走时，怎么知道以前是走那条路的？在

我在这里

 class Tree(object):

     def __init__(self, zigzags, node, left, right):
         self.zigzags = zigzags
         self.node = node
         self.left = left
         self.right = right

TREE = (5, (3, (20, (6, None, None), None), None), (10, (1, None, None), (15, (30, None, (9, None, None)), (8, None, None))))



def walk_tree(tree, current_direction='l', zigzag_count=0, this_path=''):
    left = tree[1]
    right = tree[2]

    print('left:')
    print(left)

    print('right:')
    print(right)

    print('zigzag_count:')
    print(zigzag_count)

    possible_left_path = this_path + 'l'  # say like 'lrl'
    possible_right_path = this_path + 'r' # say like 'lrr'

    if left:
        if current_direction == 'r':
            zigzag_count += 1
        return walk_tree(left, 'l', zigzag_count)

    elif right:
        if current_direction == 'l':
            zigzag_count += 1
        return walk_tree(right, 'r', zigzag_count)

    else:
        return zigzag_count

count = walk_tree(TREE)
print(count)

我相信它从左边走了下来然后停了下来：

^{pr2}$

预期答案是2，向右，向右，向左，向右走。在

我想尝试解决锯齿形的问题，只是为了学习，但是我想知道如何以这种格式递归地遍历这个二叉树，并且知道何时改变行走方式（当我再次从顶部开始时），以及它背后的一些理论（如果可能的话）。我更喜欢Python或JavaScript的示例。在

Answer 1

采用递归方法，您可以声明以下规则：

Le从当前节点开始的最长锯齿形，如果从左侧到达，则是最长的左锯齿形和最长的右侧锯齿形之间的最长值加1；反之，如果从右侧到达。在

根节点的规则不同，因为它不是从任何一侧到达的。在

def Length(Node, FromLeft):
  if Node == None:
    return 0
  return max(Length(Node.Left, True) + (1 if not FromLeft else 0), Length(Node.Left, False) + (1 if FromLeft else 0))

print max(Length(Root.Left, True), Length(Root.Right, False))

我没有利用锯齿形的区域，但这当然是可行的。在

Answer 2

这是一个典型的分而治之的问题。给定一个有子节点的节点，该节点的z字形得分是其z字形得分最高的子节点（如果到达该子节点需要改变方向，则加1）：

def zigzagscore(node):
    left, right = node[1:]

    left_zigzag, left_path = 0, ''
    if left is not None:
        left_zigzag, left_path = zigzagscore(left)
        if left_path.startswith('r'):
            # We zigged for left
            left_zigzag += 1
        left_path = 'l' + left_path

    right_zigzag, right_path = 0, ''
    if right is not None:
        right_zigzag, right_path = zigzagscore(right)
        if right_path.startswith('l'):
            # We zagged for right
            right_zigzag += 1
        right_path = 'r' + right_path

    if left_zigzag > right_zigzag:
        return left_zigzag, left_path
    else:
        return right_zigzag, right_path

当有左节点可用时，代码从不考虑正确的路径。在

这将生成预期路径：

^{pr2}$