其实二叉树的概念不难理解,之前学数据结构的时候看了概念,懂了,但是今天在做leetcode的时候遇到一个极简单的二叉树问题(leetcode链接),却不知道怎么用代码实现。
比如,用二叉树的时候,先定义节点类型(Treenode class):
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
但是,如何选择目前操作的节点,如何移动当前的节点到左边或者右边?这个问题在之前做链表的时候似乎遇到过。这些数据结构似乎是在编译器的底层写好的,一旦声明数据类型属于链表或二叉树,系统就可以自动对下一个节点赋值。
二叉树是一种非线性结构,而我们的逻辑思维习惯于线性的推理结构,因此无论是用迭代还是循环,想起来都有点费劲。尤其是循环,一般的循环i从0到n,而二叉树的循环是从root node到leaf node,想要找到遍历且还不重复的方法,从零开始还是挺不容易的。好在各路大神已经开发出了适合的算法,小辈只需要理解并且会用就成了。
官方对这个问题给出了两种解答方式:迭代和循环(Recursive and Iterative)。迭代是从root节点开始,然后分别从左边和右边调用迭代函数;循环则要用到stack,用stack.pop()和stack.append(node)来选取、操作节点。两种方法的运算速度和内存占用都类似。
另外一个问题,二叉树是如何存储的?在测试的时候,当我给出了根节点的array,并且把这个array赋值给Treenode class的一个变量后,该变量长度为1,值为根节点的值,同时该节点左右两边的节点信息也都有了。
网友评论