Basics

基本定义

  • Full binary tree: 每个节点 children = 0 or 2. 没有奇葩的单节点"拐弯"
  • Complete binary tree: 按 level order 从左到右依次（尽量）填满

Traversal

  • Preorder: 根左右

  • Inorder: 左根右

  • Postorder: 左右根

Time Complexity (Divide & Conquer)

  • 通过O(n)的时间，把n的问题，变为了n/2的问题，复杂度是多少?

    • T(n) = 2T(n/2) + o(n) = o(nlogn)

  • 通过O(1)的时间，把n的问题，变成了两个n/2的问题，复杂度是多少?

    • T(n) = 2T(n/2) + o(1) = o(n)

  • 二叉树问题一般都是 o(n)

Tips

  • 分治法解决 ~90% Tree问题!!
  • 碰到二叉树的问题，就想想整棵树在该问题上的结果 和左右儿子在该问题上的结果之间的联系是什么

遍历和分治 (Traverse (dfs?) vs Divide & Conquer)

Traverse Divide & Conquer
Recursion Algo Recursion Algo
Result in parameter (无返回值 返回值在参数里) Result in return value (有返回值 e.g. ResultType)
Top down Bottom up
e.g. DFS e.g. Merge sort / Quick Sort

"非递归其实是模拟递归用的stack 为什么自己模拟的可以, 调用计算机的就不行呢? 因为我们new出来的stack在heap memory里面, 能用的空间≈ memory size stack memory ≈ process memory是计算机分给每个程序的一个很小的独占的空间,所以递归的深度太深,就不够用了"

source: https://stomachache007.wordpress.com/2017/03/12/九章算法笔记-3-binary-tree-divide-conquer/

Problems

stack is used for store the path

Preorder: http://www.lintcode.com/en/problem/binary-tree-preorder-traversal/

  • recursion * 2 and non-recursion (stack)
  • stack: 边压边加一路左 走投无路栈往右

Inorder: http://www.lintcode.com/en/problem/binary-tree-inorder-traversal/

  • recursion * 2 and non-recursion (stack) (stack, 寻左根压栈, 取根再取右)
  • stack: 只压不加一路左 走投无路栈往右

Postorder: http://www.lintcode.com/en/problem/binary-tree-postorder-traversal/

  • recursion * 2 and non-recursion (stack)
  • stack: 边压边加一路右 走投无路栈往左

(BFS) Level Order Traversal: http://www.lintcode.com/en/problem/binary-tree-level-order-traversal/

  • 2 queues
  • 1 queue + dummy node (作为层与层隔断)
  • 1 queue (Best)
  • Queue 基本就用在BFS里 还有hashmap

Max Depth: http://www.lintcode.com/en/problem/maximum-depth-of-binary-tree/

Balanced Binary Tree: http://www.lintcode.com/en/problem/balanced-binary-tree/

  • when need ResultType?

LCA (Lowest Common Ancestor): http://www.lintcode.com/en/problem/lowest-common-ancestor/

  • with parent pointer vs no parent pointer

  • 有parent的情况 o(h) h是树的深度

  • 没有parent的情况 o(n) divide and conquer 基本都是o(n)

  • 除了node1 node2 其他都填充为空

LCA ii, LCA iii

LCA in BST: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/

Binary Tree Path Sum - exists: https://leetcode.com/problems/path-sum/description/

  • backtracking

Binary Tree Path Sum ii - all path: https://leetcode.com/problems/path-sum-ii/description/

Binary Tree Max Path Sum ii: http://www.lintcode.com/en/problem/binary-tree-maximum-path-sum-ii/

  • Root to Any

Binary Tree Max Path Sum: http://www.lintcode.com/en/problem/binary-tree-maximum-path-sum/

  • Any to Any

Binary Tree Path: http://lintcode.com/en/problem/binary-tree-paths/

  • divide and conquer
  • traverse
  • backtracking

Binary Tree Level Order Traversal ii: http://www.lintcode.com/en/problem/binary-tree-level-order-traversal-ii/

Binary Tree Zigzag Level Order Traversal: http://www.lintcode.com/en/problem/binary-tree-zigzag-level-order-traversal/

Validate Binary Search Tree: http://lintcode.com/en/problem/validate-binary-search-tree/

  • compare difference between DFS traversal vs. divide & conquer

Minimum Subtree

Flattern Binary Tree to Linked List

Binary Tree Longest Consecutive Sequence

Serialize and Deserialize Binary Tree (BFS & DFS)

二叉树

给出一棵Binary Tree的字符串表示，比如[1,[2,3]]，还原这棵二叉树（高频）【系统班的作业题】

给出一棵Binary Tree的先序和中序遍历序列，还原这棵二叉树

http://www.lintcode.com/en/problem/construct-binary-tree-from-preorder-and-inorder-traversal/

给出一棵Binary Tree，按照深度（同样深度从左往右）遍历并输出结果

http://www.lintcode.com/en/problem/binary-tree-level-order-traversal/

给出一棵Binary Tree，输出每一条从根节点到叶子节点的路径

http://www.lintcode.com/en/problem/binary-tree-paths/

给出一棵Binary Tree，输出与之镜面对称的二叉树

给出两棵Binary Tree，判断这两棵二叉树是否完全一样（形状和每个点的value都要相同才算完全一样）

http://www.lintcode.com/en/problem/identical-binary-tree/

给出两棵Binary Tree，A和B，判断B是否为A的子树

http://www.lintcode.com/en/problem/subtree/

分治法

求一棵二叉树的最大深度（分治思想的简单应用）

http://www.lintcode.com/en/problem/minimum-depth-of-binary-tree/

给出一棵Binary Tree，求出这棵二叉树上和最大的路径

http://www.lintcode.com/en/problem/binary-tree-maximum-path-sum

给出一棵Binary Search Tree，问是否是Balanced Binary Search Tree

http://www.lintcode.com/en/problem/balanced-binary-tree/

合并k个排好序的List（高频）

http://www.lintcode.com/en/problem/merge-k-sorted-lists/

求一个Array中的中位数（高频，partition方法）

http://www.lintcode.com/en/problem/median/

给出两个排好序的List，输出这两个序列中的中位数，如果存在两个中位数则输出这两个数的平均数

http://www.lintcode.com/en/problem/median-of-two-sorted-arrays/

给出一个Array，求出Array中的每个元素的右边比其小的元素个数（归并排序应用）

http://www.lintcode.com/en/problem/reverse-pairs/

results matching ""

    No results matching ""