其实二叉树的概念不难理解, 之前学数据结构的时候看了概念, 懂了, 但是今天在做 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, 值为根节点的值, 同时该节点左右两边的节点信息也都有了.
来源: http://www.jianshu.com/p/e971405be065