Tree Traversal

二叉树的遍历，前、中、后、层、等各种遍历的非递归写法也要非常的熟练。经常要用到的就是二分查找的时候，根据构造的条件进行继续二分，能够一眼看到用什么构造二分的条件非常的重要。

230. Kth Smallest Element in a BST

经典的的inorder递归做法就不记录了。 非递归Inorder Traversal：

int kthSmallest(TreeNode* root, int k) {
    stack<TreeNode*> st;
    TreeNode* node = root;
    while(node || !st.empty()) {
        while (node) {
            st.push(node);
            node = node->left;
        }
        node = st.top();
        st.pop();
        if (--k == 0) return node->val;
        node = node->right;
    }
}

构造条件的Binary Search:查找左子树的节点数，如果左子树的节点数刚好为k-1则当前节点即为所找。

int kthSmallest(TreeNode* root, int k) {
    if (!root) return -1;
    int cnt = countNode(root->left);
    if (k == cnt + 1) return root->val;
    else if (k < cnt + 1) return kthSmallest(root->left, k);
    else return kthSmallest(root->right, k-cnt-1);
}

int countNode(TreeNode* root) {
    if (!root) return 0;
    return 1 + countNode(root->left) + countNode(root->right);
}

222. Count Complete Tree

基本上只要是树的问题，都会涉及到递归的解法。先构造基本case，再递归。 Solution from this link

int countNodes(TreeNode* root) { // 
    if (!root) return 0;
    TreeNode* l = root;
    TreeNode* r = root;
    int left_cnt = 0;
    int right_cnt = 0;
    while (l) { ++left_cnt; l = l->left;}
    while (r) { ++right_cnt; r = r->right;}
    if (left_cnt == right_cnt) return (1<<left_cnt) - 1;
    else return 1 + countNodes(root->left) + countNodes(root->right);
}

255. Verify Preorder Sequence in Binary Search Tree

Solution from link

Kinda simulate the traversal, keeping a stack of nodes (just their values) of which we're still in the left subtree. If the next number is smaller than the last stack value, then we're still in the left subtree of all stack nodes, so just push the new one onto the stack. But before that, pop all smaller ancestor values, as we must now be in their right subtrees (or even further, in the right subtree of an ancestor). Also, use the popped values as a lower bound, since being in their right subtree means we must never come across a smaller number anymore.

bool verifyPreorder(vector<int>& preorder) {
    if (!preorder.size()) return true;
    stack<int> st;
    int low = INT_MIN;
    for (auto n : preorder) {
        if (n < low) return false;
        while (!st.empty() && n > st.top()) {
            low = st.top();
            st.pop();
        }
        st.push(n);
    }

    return true;
}

272. Closest Binary Search Tree Value II

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> closestKValues(TreeNode* root, double target, int k) {
        vector<int> res;
        stack<TreeNode*> lower;
        stack<TreeNode*> upper;
        TreeNode* cur = root;

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

        while (res.size() != k) {
            if (lower.empty()) {
                auto top = getSuccessor(upper);
                if (top) res.push_back(top->val);
            } else if (upper.empty()) {
                auto top = getPredecessor(lower);
                if (top) res.push_back(top->val);
            } else {
                int l = lower.top()->val;
                int r = upper.top()->val;
                if (fabs(static_cast<double>(l) - target) < fabs(static_cast<double>(r) - target)) {
                    res.push_back(l);
                    getPredecessor(lower);
                } else {
                    res.push_back(r);
                    getSuccessor(upper);
                }
            }
        }

        return res;
    }

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

    TreeNode* getSuccessor(stack<TreeNode*>& suc) {
        if (!suc.size()) return nullptr;

        auto cur = suc.top();
        auto ret = cur;
        suc.pop();
        cur = cur->right;
        while (cur) {
            suc.push(cur);
            cur=cur->left;
        }
        return ret;
    }
};