Tree

Preorder traversal 前序遍历
inorder traversal 中序遍历 
Postorder 后序
中序遍历
  • 数据结构:stack
  • root压栈,查找左子树直至=None,中间结点,右子树
先左子树,后根节点,最后访问右子树
后序遍历:
  • uses modified preorder (right subtree first). Then reverse the result.
一份比较全的总结:
BST:Binary Search Tree

二叉树,二叉搜索树:

总结的比较完整的博客:

Level Order Traversal 层序遍历

109. Convert Sorted List to Binary Search Tree

  • 找头结点,用two pointers找
  • 然后断开左右链表,左边作为左子树,右边作为右子树

95. Unique Binary Search Tree II

  • tree = [] 输出所有可能构造出的树
    
  •     c = 1
  •     for i in range(n):
  •         c = c*2*(2*i+1)/(i+2)    #计算公式

98. Validate Binary Search Tree

  • 出错的测试数据:[10,5,15,null,null,6,20]右子树的子节点小于根节点   [0,-1] 一边有left子树,一边为NULL
  • 解法:1. 中序遍历输出到数组,判断数组是否是a1<a2<a3<...<an

104. Maximum Depth of Binary Tree

  • 1. DFS 
  • 2. 层序遍历的做法

构建树

105. Construct Binary Tree from Preorder and Inorder Traversal

  • preorder[0]一定是根节点,在inorder中找到根节点再分左右子树做
立即登录, 发表评论.
没有帐号? 立即注册