二叉树

其实二叉树的概念不难理解，之前学数据结构的时候看了概念，懂了，但是今天在做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，值为根节点的值，同时该节点左右两边的节点信息也都有了。