查找二叉搜索树的叶子节点

[编程题]查找二叉搜索树的叶子节点

热度指数：1459 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给一个二叉查找树（Binary Search Tree）的前序遍历结果数组，打印出所有的叶子节点。

输入描述:

输入为二叉查找树的前序遍历结果数组，元素之间用空格分隔：

9 8 7 10

输出描述:

所有的叶子节点元素，用空格分隔

解释：因为二叉搜索树的表示为:

8 10

输出的叶子节点为: 7 10

示例1

输入

9 8 7 10

输出

7 10

算法知识视频讲解

Python

卡瓦夏日

tree=list(map(int,input().split()))
#tree=[40, 31, 25, 20, 26, 33, 50, 42, 53]
def findt(tree):
    if len(tree)<2:
        #return str(tree)
        return tree
    i=1
    while (i<len(tree)) and tree[i]<=tree[0]:
        i+=1
    if i==len(tree):
        return [tree[-1]]
    else:
        return findt(tree[1:i])+findt(tree[i:])
a=findt(tree)
a=list(map(str,a))
#for i in a:
#    res+=' '+str(i)
#print(res)
print(' '.join(a))

思路参考 https://blog.csdn.net/u013616945/article/details/68927716

二叉搜索树：空树或者满足下列条件：

若左子树不空，则左子树上所有结点的值都小于根节点。
若右子树不空，则右子树上所有结点的值都大于根节点。
为了判断一个数组是否为一棵二叉搜索树的前序遍历，主要思想为：因前序遍历第一个遍历的是根节点，则数组第一个数为根节点的值，再基于根节点把整棵树的遍历序列分成左子树和右子树序列，递归的处理这两个子序列。

发表于 2021-04-19 17:54:50 回复(0)