Tree

Tree 的解法基本上主要集中在递归,其中 post order traversal 这种递归更为常见, 处理 Tree 相关的问题, 一般比较优化的方法就是遍历一次完成, 也就是先处理左右子树,然后在处理自身.

树的性质篇

General Tree

这个总结的挺好的,数的性质: 深度,是否平衡,是否对称,是否一样等等

1. Balanced Binary Tree
2. Maximum Depth of Binary Tree
3. Minimum Depth of Binary Tree
4. Symmetric Tree
5. Same Tree

Minimum Depth of Binary Tree 这一题要考虑根节点只有一个child 的情况

BST 的性质

1. Validate Binary Search Tree 这个题目的解法有两种,一种是使用 inorder的遍历, 如果 inorder 遍历的值是上升的,则是 valid 的 BST, 前提是 BST 中没有重复, 如果有重复则无法保证重复是出现在 bst 的同一边, 则无法判断是不是 valid. 另外一种就是 preorder 的遍历, 每次遍历总保证当前节点的值处于最大最小之间,但是要处理INT_MAX和INT_MIN的问题, 需要使用 long long 来保存最大最小值. 下面这个解法比较好的避免了处理最大最小值的问题.

bool isValidBST(TreeNode* root) {
    return isValidBST(root, NULL, NULL);
}

bool isValidBST(TreeNode* root, TreeNode* minNode, TreeNode* maxNode) {
    if(!root) return true;
    if(minNode && root->val <= minNode->val || maxNode && root->val >= maxNode->val)
        return false;
    return isValidBST(root->left, minNode, root) && isValidBST(root->right, root, maxNode);
}

1. Verify Preorder Sequence in Binary Search Tree 遇到比栈顶小的，那是左子树，直接push进stack。遇到比栈顶大的，说明进到右子树， 就要找当前元素的predecessor：pop出所有比当前元素小的元素，最后一个pop的就是当前元素的parent，那接下来所有的元素都要比这个parent大，因为他的左子树已经visit完成了（已经到右子树了）

bool verifyPreorder(vector<int>& preorder) {
    size_t len = preorder.size();
    if (!len) return true;

    stack<int> st;
    int cur_min = INT_MIN;
    for (auto node : preorder) {
        if (node < cur_min) return false;

        while (!st.empty() && st.top() < node) {
            cur_min = st.top();
            st.pop();
        }
        st.push(node);
    }
    return true;
}

1. Unique Binary Search Trees

2. Unique Binary Search Trees II

树的遍历篇

基本是(preorder/inorder/post order/level order)四中遍历的递归和非递归的写法都要掌握, post order 的非递归方法比较难理解,需要总结一下.

[更简单的非递归遍历二叉树的方法](http://zisong.me/post/suan-fa/geng-jian-dan-de-bian-li-er-cha-shu-de-fang-fa) 提供了一个统一的非递归的遍历方法,但是感觉貌似不是很容易说的让别人能很快理解, 面试的时候假如需要证明需要考虑下怎么解释.

level order (BFS)

由于是 BFS 搜索,所有有很多相关的题目

1. Binary Tree Level Order Traversal

2. Binary Tree Level Order Traversal II

3. Binary Tree Right Side View

4. Populating Next Right Pointers in Each Node

5. Populating Next Right Pointers in Each Node II

preorder(DFS)

处理preorder有点像 level order先处理自己, 然后再把结果带到下一层,这个和 post order 的很多解法刚刚相反. 不过也应该能够根据题目很自然的想到两种的不同: 子节点依赖父节点的, 那么就 preorder; 反之, 父节点的状态依赖子节点的, 则使用 post order.

1. Binary Tree Preorder Traversal

2. Binary Tree Paths

3. Path Sum

4. Path Sum II

5. Binary Tree Longest Consecutive Sequence

6. Flatten Binary Tree to Linked List

7. House Robber III

8. Serialize and Deserialize Binary Tree

9. Sum Root to Leaf Numbers

10. Validate Binary Search Tree

inorder(DFS)

1. Closest Binary Search Tree Value 主要是利用 BST 的特性, 在查找的时候进行二分, 要主要比较的是当前节点和目标值的差距以及自己的一个子节点(二分后)与目标值的差距,递归找出最小的.

2. Closest Binary Search Tree Value II 思路和上面一题类似,但是主要问题在于找到 insert position 后, 需要有方法去successor 和 predecessor. 方法就是在二分的时候将大于的节点放到 successor的 stack 里面, 小于的放到 predecessor 的 stack 里面.

   while (cur) {
    if (target < static_cast<double>(cur->val)) {
        successor.push(cur);
        cur = cur->left;
    } else {
        predecessor.push(cur);
        cur = cur->right;
    }
   }
   

   然后实现下面的方法. 主要是思想是predecessor是当前节点的左节点的最右节点. pop 一个 predecessor 后,依次将其左节点的右子节点入栈. successor 则是将右节点的左子节点入栈.

TreeNode* getPredecessor(stack<TreeNode*>& predecessor) {
    if (predecessor.empty()) return nullptr;
    auto ret = predecessor.top();
    predecessor.pop();
    TreeNode* cur = ret->left;
    while (cur) {
        predecessor.push(cur);
        cur = cur->right;
    }

    return ret;
}

TreeNode* getSuccessor(stack<TreeNode*>& successor) {
    if (successor.empty()) return nullptr;

    auto ret = successor.top();
    successor.pop();
    TreeNode* cur = ret->right;
    while (cur) {
        successor.push(cur);
        cur = cur->left;
    }

    return ret;
}

1. Kth Smallest Element in a BST, 另外一个解法就是order statistic tree的方法.

2. Recover Binary Search Tree 使用 inorder 遍历来找出翻转的两个, 这个时候就需要通过例子来帮助解决问题, 有两种情况, 一是翻转的两个是挨着的, 另外就是不是挨着的, 两种情况下两个节点的 index 的获取方式不一样.这个只有通过例子才能很好的处理.

post order(DFS)

1. Binary Tree Postorder Traversal

2. Balanced Binary Tree

3. Count Univalue Subtrees

4. Largest BST Subtree

非常经典的一题.

1. 首先,要判断一个树是否为 BST, 则需要判断它的左右子树分别是不是 BST, 涉及到依赖子树的状态的判断,就是 post order traversal.
2. 判断的过程中还需要保存节点的数目,因为题目需要返回节点数.
3. 不同于 preorder 来判断是不是 BST, post order需要返回子节点的最大值和最小值, 这样才能判断当前节点是不是处于正确的范围.

处理的方法就是每次递归都返回上面这些需要的信息, 可以通过返回一个数据结构,通过指针或者引用来进行返回.

1. Lowest Common Ancestor of a Binary Tree

2. Path Sum post order的做法其实比较不好理解, preorder也可以做

其它的遍历包括:

1. Binary Tree Right Side View

2. Binary Tree Zigzag Level Order Traversal

3. Binary Tree Maximum Path Sum

   变化比较大而且有点难度的是Binary Tree Maximum Path Sum，这道题目的路径要求不再是从根到叶子的路径，这个题目是把树完全看成一个无向图，然后寻找其中的路径。想起来就觉得比上面那种麻烦许多，不过仔细考虑会发现还是有章可循的，找到一个根节点最大路径，无非就是找到左子树最大路径，加上自己的值，再加上右子树的最大路径（这里左右子树的路径有可能不取，如果小于0的话）。我们要做的事情就是对于每个结点都做一次上面说的这个累加。而左子树最大路径和右子树最大路径跟Path Sum II思路是比较类似的，虽然不一定要到叶子节点，不过标准也很简单，有大于0的就取，如果走下去路径和小于0那么就不取。从分治的角度来看，左右子树的最大路径就是取自己的值加上Max(0，左子树最大路径，右子树最大路径)。这么一想也就不用考虑那么多细节了。而通过当前节点的最长路径则是自己的值+Max(0，左子树最大路径)+Max(0，右子树最大路径)。所以整个算法就是维护这两个量，一个是自己加上左或者右子树最大路径作为它的父节点考虑的中间量，另一个就是自己加上左再加上右作为自己最大路径。具体的实现可以参见Binary Tree Maximum Path Sum。分析来源于link

Iterator

Iterator基本上是上面的遍历的数据结构实现版本, 主要用于二叉树中的前驱/后继/父等节点的遍历. 一般就是使用 stack 模拟前面的遍历的过程

1. Binary Search Tree Iterator

2. Closest Binary Search Tree Value

3. Closest Binary Search Tree Value II

4. Inorder Successor in BST 很容易想到的就是 inorder traversal 一遍, 复杂度是O(N), 下面的方法是O(logN)

TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
    if (!root || !p) return root;
    if (root->val <= p->val) return inorderSuccessor(root->right, p);
    auto left = inorderSuccessor(root->left, p);
    return left ? left : root;
}

网上的 java 版本

public TreeNode successor(TreeNode root, TreeNode p) {
  if (root == null)
    return null;

  if (root.val <= p.val) {
    return successor(root.right, p);
  } else {
    TreeNode left = successor(root.left, p);
    return (left != null) ? left : root;
  }
}

public TreeNode predecessor(TreeNode root, TreeNode p) {
  if (root == null)
    return null;

  if (root.val >= p.val) {
    return predecessor(root.left, p);
  } else {
    TreeNode right = predecessor(root.right, p);
    return (right != null) ? right : root;
  }
}

树的构造篇

1. Construct Binary Tree from Preorder and Inorder Traversal

2. Construct Binary Tree from Inorder and Postorder Traversal
   这两题的解法是一样的, 就是通过 preorder 和 post order 进行构造节点, 使用 inorder 定位左右子树.

3. Convert Sorted Array to Binary Search Tree

4. Binary Tree Upside Down

5. Invert Binary Tree

Binary Search

1. Count Complete Tree Nodes
   这一题也是比较精妙的, 使用递归不停的查看左右子树的最左和最右的深度.

2. Lowest Common Ancestor of a Binary Search Tree