二叉树专题

二叉树3大遍历：先序，中序，后序
非递归版本：https://www.jianshu.com/p/373a002c401b

先序：
class Solution {
public:
    vector<int> ans;
    std::stack<TreeNode *> s;
    vector<int> preorderTraversal(TreeNode * root) {
        // write your code here
        auto cur=root;
        while(cur||s.size())
        {
            while(cur)
            {
                ans.push_back(cur->val);
                s.push(cur);
                cur=cur->left;
            }
            cur=s.top();
            s.pop();
            cur=cur->right;
        }
        return ans;
    }
};

中序
class Solution {
public:
    /**
     * @param root: A Tree
     * @return: Inorder in ArrayList which contains node values.
     */
    vector<int> ans;
    stack<TreeNode *> s;
    vector<int> inorderTraversal(TreeNode * root) {
        // write your code here
        auto cur=root;
        while(cur||s.size())
        {
            while(cur)
            {
                s.push(cur);
                cur=cur->left;
            }
            cur=s.top();
            s.pop();
            ans.push_back(cur->val);
            cur=cur->right;
        }
        return ans;
    }
};

后序遍历
class Solution {
public:
    /**
     * @param root: A Tree
     * @return: Postorder in ArrayList which contains node values.
     */
    vector<int> ans;
    std::stack<TreeNode *> s;
    vector<int> postorderTraversal(TreeNode * root) {
        // write your code here
        auto cur=root;
        TreeNode * last=NULL;
        while(cur||s.size())
        {
            while(cur)
            {
                s.push(cur);
                cur=cur->left;
            }
            cur=s.top();
            if(cur->right==NULL||cur->right==last)
            {
                ans.push_back(cur->val);
                s.pop();
                last=cur;
                cur=NULL;
            }
            else
                cur=cur->right;
        }
        return ans;
    }
};

236. 二叉树的最近公共祖先