145. Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes’ values.

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [3,2,1]

Follow up: Recursive solution is trivial, could you do it iteratively?

实现二叉树的后续遍历算法，需要非递归形式哦~这题好难…是三种非递归遍历算法中最难的一种了。
惯例，先上递归算法：

class Solution {
public:
    void work(vector<int>& ans, TreeNode* root)
    {
        if (root == NULL)
            return;
        work(ans, root->left);
        work(ans, root->right);
        ans.push_back(root->val);
    }
    vector<int> postorderTraversal(TreeNode* root)
    {
        vector<int> ans;
        work(ans, root);
        return ans;
    }
};

本代码提交AC，用时3MS。
下面来想非递归算法。后续遍历的顺序是：左右根，根节点是最后访问的。还是用堆栈来实现，那么根据堆栈的后进先出性质，压栈的顺序应该是根右左。
那么什么时候可以访问根节点呢，只有当这个节点是叶子节点或者左右孩子都访问完之后才可以。判断是否为叶子节点很容易，那么怎么判断左右孩子都访问完了呢，此时我们可以用一个变量pre来记录上一次访问的节点，curr为当前栈顶节点。如果pre是curr的左或右孩子节点，则说明左右孩子已经访问过了，此时我们就可以访问curr了。
本算法的代码如下：

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root)
    {
        vector<int> ans;
        if (root == NULL)
            return ans;
        stack<TreeNode*> tree;
        TreeNode *curr, *pre = NULL;
        tree.push(root); // 根
        while (!tree.empty()) {
            curr = tree.top();
            if ((curr->left == NULL && curr->right == NULL) || // 已到叶子节点
                (pre != NULL && (curr->left == pre || curr->right == pre))) { // 回溯的时候
                ans.push_back(curr->val);
                tree.pop();
                pre = curr;
            }
            else {
                if (curr->right != NULL)
                    tree.push(curr->right); // 右
                if (curr->left != NULL)
                    tree.push(curr->left); // 左
            }
        }
        return ans;
    }
};

本代码提交AC，用时0MS。

可能有同学担心curr->left==pre不能一定说明左右孩子都访问完了，只能说明左孩子访问完了。但是根据我们的压栈顺序，当curr同时又左右孩子的时候，不会走这条判断。如下左图所示，首先4会弹栈，然后栈顶变为了5，此时pre=4, curr=5，访问5；然后5弹栈，栈顶为2，此时pre=5,curr=2，所以走的是curr->right==pre，访问2。只有当curr只有左孩子没有右孩子的时候才会判断curr->left==pre，如下右图，此时是可以访问curr的。

还有一种很简洁漂亮的解法，用两个堆栈。再次回忆后序遍历顺序：左右根，我们怎样用两个堆栈得到这样的顺序呢。如下图所示，第一个堆栈压栈顺序是左右根，然后弹出来压到第二个堆栈里，则从第二个堆栈里弹出来的顺序就是左右根了。注意，虽然第一次压栈的顺序已经是左右根了，我们要得到的也是左右根，为什么还要经过第二个堆栈这样倒腾一下呢？因为堆栈1的左右根和从堆栈2出来的左右根是不一样的，前者是靠近根节点的左右根，但是我们的后序遍历是要从叶子节点开始得到左右根，而从堆栈2出来的就是从叶子节点开始的左右根。

下面结合代码来说：

 class Solution {
   public: vector < int > postorderTraversal(TreeNode * root) {
     vector < int > ans;
     if (root == NULL) return ans;
     stack < TreeNode * > s1, s2;
     TreeNode * top;
     s1.push(root); // 根 
     while (!s1.empty()) {
       top = s1.top(); // (1)
       s1.pop(); // (1)
       s2.push(top); // (1)
       if (top - > left != NULL) {
         // 左
         s1.push(top - > left);
       }
       if (top - > right != NULL) {
         // 右 
         s1.push(top - > right);
       }
     }
     while (!s2.empty()) {
       top = s2.top();
       ans.push_back(top - > val);
       s2.pop();
     }
     return ans;
   }
 };

从第13、16行可知，对于堆栈1，我们先压了左后压了右，但是从第8行来看，根是最先压的，看起来不符合左右根的压栈顺序，但是请注意，代码(1)部分在先于13、16行弹栈了，然后马上压到堆栈2了，这样的效果不就是根节点在堆栈1的栈顶，然后被压到了堆栈2的底部了吗。所以和上图是统一的。

本代码提交AC，用时0MS。
定睛一看，这居然是道hard题。。。

三刷。这一题和中序遍历的迭代解法很类似。后序遍历是左右根，依然是要最先访问左子树的左叶子，所以依然可以使用函数putAllLeft将根沿着左子树的节点都放到栈中，只是在弹栈访问时，需要注意，如果该节点的右孩子已经访问，则无需再调用putAllLeft了，否则会导致死循环。所以在访问某个节点时，记录一下，存到pre中，作为下一个节点访问时上一个访问的节点。如果当前要访问的右孩子为pre，则说明右孩子已经访问过了，无需对右孩子调用putAllLeft。

完整代码如下：

class Solution {
public:
	void PutAllLeft(TreeNode *root, stack<TreeNode*> &stk) {
		while (root != NULL) {
			stk.push(root);
			root = root->left;
		}
	}
	vector<int> postorderTraversal(TreeNode* root) {
		vector<int> ans;
		stack<TreeNode*> stk;
		PutAllLeft(root, stk);
		TreeNode *pre = NULL;
		while (!stk.empty()) {
			TreeNode *cur = stk.top();
			if (cur->right != NULL && cur->right != pre) {
				PutAllLeft(cur->right, stk);
			}
			else {
				ans.push_back(cur->val);
				stk.pop();
				pre = cur;
			}
		}
		return ans;
	}
};

本代码提交AC，用时0MS。

144. Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes’ values.

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,2,3]

Follow up: Recursive solution is trivial, could you do it iteratively?

这一题要实现二叉树的前序遍历，前序遍历的顺序是：根左右。
首先献上妇孺皆知的递归解法：

class Solution {
public:
    void work(vector<int>& ans, TreeNode* root)
    {
        if (root == NULL)
            return;
        ans.push_back(root->val);
        work(ans, root->left);
        work(ans, root->right);
    }
    vector<int> preorderTraversal(TreeNode* root)
    {
        vector<int> ans;
        work(ans, root);
        return ans;
    }
};

本代码提交AC，用时3MS。和LeetCode Binary Tree Inorder Traversal一样，本题也要实现前序遍历的迭代算法。迭代的思路同样是用堆栈来实现：首先把当前根节点压栈，然后注意，因为前序遍历是先访问左子树，后访问右子树，所以我们压栈的时候，要先压右子树，再压左子树，这样弹栈的时候才能符合前序遍历的要求。除此之外，我觉得实现起来比中序遍历要简单。
迭代版本的完整代码如下：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root)
    {
        vector<int> ans;
        if (root == NULL)
            return ans;
        stack<TreeNode*> tree;
        tree.push(root);
        TreeNode* top;
        while (!tree.empty()) {
            top = tree.top();
            ans.push_back(top->val);
            tree.pop();
            if (top->right != NULL) { // 先压栈右子树
                tree.push(top->right);
            }
            if (top->left != NULL) { // 再压栈左子树
                tree.push(top->left);
            }
        }
        return ans;
    }
};

本代码提交AC，用时也是3MS。

94. Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes’ values.

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,3,2]

Follow up: Recursive solution is trivial, could you do it iteratively?

本题要实现二叉树的中序遍历。这个题应该是很基本的二叉树的遍历题，本科学数据结构对这个是基本要求。不过本科学的是中文教材，只知道前序、中序、后序，不知道对应的英文是什么，WIKI上的Tree traversal图解还是很通俗易懂的：前序（Pre-order），中序（In-order），后序（Post-order）和层次遍历（Level-order）。
前序、中序和后序的区别很容易记，只要记住他们的前、中、后分别是访问根节点的顺序。比如前序顺序是先访问根节点，然后依次访问左右孩子节点。前序：根左右；中序：左根右；后序：左右根。
本题要实现二叉树的中序遍历，如上所述，先访问左子树，然后访问根节点，最后访问右子树。用递归的方法非常简洁直观。递归的完整代码如下：

class Solution {
public:
    void work(vector<int>& ans, TreeNode* root)
    {
        if (root == NULL)
            return;
        work(ans, root->left); // 左
        ans.push_back(root->val); // 根
        work(ans, root->right); // 右
    }
    vector<int> inorderTraversal(TreeNode* root)
    {
        vector<int> ans;
        work(ans, root);
        return ans;
    }
};

本代码提交AC，用时0MS。

但是Note问能不能用迭代实现以下呢？当然可以，所以可以用递归实现的算法肯定都可以用迭代的方法实现，只是有时候迭代写起来更麻烦。
我的思路是肯定要首先找到树的最左下角的叶子节点，这个节点是最先被访问的，然后访问根节点，最后访问右子树。访问右子树的时候，又是重复之前的操作，首先找到右子树中的最左下角的叶子节点，访问它，然后访问根节点，最后又访问其右子树。
上述过程需要在访问完左孩子之后再访问根节点，但是树中节点的指向是单向的，只能由根访问到孩子，不能由孩子回溯到根。我们不可能在找孩子的同时保存该孩子的父亲节点，这样太麻烦了。于是我想到了用堆栈，在找最左下角的叶子节点的时候，顺便把经过的祖先节点压到堆栈中，当访问完孩子节点后，弹栈，此时的栈顶节点就是父亲节点了。如果父节点有右子树，则进入右子树，重复之前的过程（找右子树的最左下角叶子）。
迭代法的完整代码如下：

class Solution {
public:
    void putAllLeft(TreeNode* root, stack<TreeNode*>& tree)
    {
        while (root != NULL) {
            tree.push(root);
            root = root->left;
        }
    }
    vector<int> inorderTraversal(TreeNode* root)
    {
        vector<int> ans;
        stack<TreeNode*> tree;
        putAllLeft(root, tree); // 找最左边的叶子节点
        TreeNode* top;
        while (!tree.empty()) {
            top = tree.top();
            ans.push_back(top->val); // 访问左（根）节点
            tree.pop();
            putAllLeft(top->right, tree); // 访问右节点
        }
        return ans;
    }
};

本代码提交AC，用时0MS。
调试的时候可以使用我之前写过的由数组生成二叉树的函数，挺方便的。

100. Same Tree

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

Input:     1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

Output: true

Example 2:

Input:     1         1
          /           \
         2             2

        [1,2],     [1,null,2]

Output: false

Example 3:

Input:     1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

Output: false

判断两棵二叉树是否相同。我第一想到的是对两棵树都先序遍历一下，然后看看遍历出来的序列是否一致，如果一致则树是一样的。

class Solution {
public:
    void preOrderTraverse(TreeNode* t, vector<int>& res)
    {
        if (t != NULL) {
            res.push_back(t->val);
            preOrderTraverse(t->left, res);
            preOrderTraverse(t->right, res);
        }
    }
    bool isSameTree(TreeNode* p, TreeNode* q)
    {
        vector<int> pRes, qRes;
        preOrderTraverse(p, pRes);
        preOrderTraverse(q, qRes);
        if (pRes.size() != qRes.size())
            return false;
        for (int i = 0; i < pRes.size(); i++) {
            if (pRes[i] != qRes[i])
                return false;
        }
        return true;
    }
};

但是这样做居然是错的！请注意，虽然两棵树的遍历结果是一样的，并不代表这两棵树的结构是一样的。比如[10,5,15]和[10,5,null,null,15]，虽然先序遍历的结果都是10,5,15，但是这两棵树的结构是不一样的。所以不能只看遍历的结果，在遍历的时候就要判断是否相同。如果在同一个位置上，一颗节点为空，另一棵上有值，结构就不一样了。要么两个节点都为空或者有值且相等。
完整代码如下：

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q)
    {
        if (p == NULL && q == NULL)
            return true;
        if (p == NULL || q == NULL)
            return false;
        if (p->val != q->val)
            return false;
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

本代码提交AC，用时0MS。