树

20.Jun.2019 Update:

写递归的重点在于先提取出题目的核心逻辑，再根据这个逻辑写出会造成问题/溢出的base case，具体例子参见

难点：写递归，有返回值的递归，没有返回值的递归，作为helper函数的递归等等。用迭代的话要注意数据结构，用栈还是队列。

操作：迭代（用栈或者队列），递归。迭代比较快，递归代码少。有些写法是二分法的变形。

  • 递归三连：前中后序遍历，level遍历 144，94，145, 102, 897(inorder变形), 114

  • same || symmetric || invert || merge: 100, 101, 226, 617,

二叉树的性质:

  • depth: 104(二叉树最大深度和最远距离), 110(判断平衡二叉树), 111
  • nodes: 222, 872
  • path(dfs): 129, 112, 113, 257

二叉搜索树:

  • search, insert, delete: 700, 701, 450
  • validate: 98
  • trim: 669

LCA: 235, 236

构建二叉树:

  • 108(sorted数组), 654(root最大), 105, 106

树有什么用：把目录代到以上所有的算法中看有什么用。如level order traversal可以用来统计各级目录下的目录和文件。

代码片段

  • 用来保留其中某个非空子树的结构，在617(merge), 450(delete)出现过，另外在merge链表里也出现过。
if (t1 == null || t2 == null) {
    return (t1 == null) ? t2 : t1;
}

另外在237(lca)中不用加判断条件是因为它前面的条件root.left != null && root.right != null已经排除了另外一种状况。

return (root.left == null) ? root.right : root.left;

Java中的API

Java LinkedList queue:

Java LinkedList stack:

results matching ""

    No results matching ""