88、二叉树前中后遍历⼿撕代码（递归和⾮递归）

LeetCode 144. ⼆叉树的前序遍历

给你⼆叉树的根节点

示例 1：

例子1：
输⼊：root = [1,null,2,3]
输出：[1,2,3]

例子2：
输⼊：root = []
输出：[]

例子3：
输⼊：root = [1]
输出：[1]

【思路】由于“中左右”的访问顺序正好符合根结点寻找⼦节点的顺序，因此每次循环时弹栈，输出此弹栈结点并将其右结点和左结点按照叙述顺序依次⼊栈。⾄于为什么要右结点先⼊栈，是因为栈后进先出的特性。右结点先⼊栈，就会后输出右结点。

初始化：⼀开始让root结点先⼊栈，满⾜循环条件

步骤：弹栈栈顶元素，同时输出此结点当前结点的右结点⼊栈当前结点的左结点⼊栈重复上述过程结束条件：每次弹栈根结点后⼊栈⼦结点，栈为空时则说明遍历结束。

//递归版
/* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x),
left(left), right(right) {}
* };
*/
class Solution {
public:
 vector<int> ans;
 vector<int> preorderTraversal(TreeNode* root) {
 // 为空则直接返回
 if(root == NULL)
 return ans;
 ans.push_back(root->val);
 preorderTraversal(root->left);
 preorderTraversal(root->right);
 return ans;
 }
}
//⾮递归
class Solution {
public:
 std::vector<int>preorderTraversal(TreeNode* root) {
 std::vector<int>res;
 if (!root) return res;
 stack<TreeNode*> st;
 TreeNode* node = root;
 while (!st.empty() || node) {
 while(node) {
 st.push(node);
 res.push_back(node->val);
 node = node->left;
 }
node = st.top();
 st.pop();
 node = node->right;
 }
 return res;
 }
};

LeetCode 94. ⼆叉树的中序遍历

难度简单1035

给定⼀个⼆叉树的根节点 root ，返回它的中序遍历。

示例 1：

输⼊：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输⼊：root = []
输出：[]

示例 3：

输⼊：root = [1]
输出：[1]

示例 4：

输⼊：root = [1,2]
输出：[2,1]

示例 5：

输⼊：root = [1,null,2]
输出：[1,2]

【思路】

中序遍历思路相较于前序遍历有很⼤的改变。前序遍历遇到根结点直接输出即可，但中序遍历 “左中右”需先找到此根结点的左结点，因此事实上第⼀个被输出的结点会是整个⼆叉树的最左侧结点。

依据这⼀特性，我们每遇到⼀个结点，⾸先寻找其最左侧的⼦结点，同时⽤栈记录寻找经过的路径结点，这些是输出最左侧结点之后的返回路径。

之后每次向上层⽗结点返回，弹栈输出上层⽗结点的同时判断此结点是否含有右⼦结点，如果存在则此右结点⼊栈并到达新的⼀轮循环，对此右结点也进⾏上述操作。初始化： curr定义为将要⼊栈的结点，初始化为root top定义为栈顶的弹栈结点步骤：

寻找当前结点的最左侧结点直到curr为空（此时栈顶结点即为最左侧结点）弹栈栈顶结点top并输出判断top是否具有右结点，如果存在则令curr指向右结点，并在下⼀轮循环入栈

重复上述过程结束条件：这⾥可以看到结束条件有两个：栈为空， curr为空。这是因为中序遍历优中后右的特性，会有⼀个时刻栈为空但右结点并未被遍历，因此只有在curr也为空证明右结点不存在的情况下，才能结束遍历。【代码】

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), 
left(left), right(right) {}
 * };
 */
 
//递归法
// class Solution {
// public:
//     std::vector<int> ret;
//     vector<int> inorderTraversal(TreeNode* root) {
//         postOrder(root);
//         return ret;
//     }
//     void postOrder(TreeNode* root) {
//         if (root == nullptr) return;
//         inorderTraversal(root->left);
//         ret.push_back(root->val);
//         inorderTraversal(root->right);
//     }
// };
 
 
//迭代法
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode*> stk;
        TreeNode* curr = root;
        while(!stk.empty() || curr != NULL) {
            // 找到节点的最左侧节点，同时记录路径⼊栈
            while(curr != NULL) {
                stk.push(curr);
                curr = curr->left;
            }
            // top 定义是此刻的弹栈元素
            TreeNode* top = stk.top();
            ans.push_back(top->val);
              stk.pop();
            // 处理过最左侧结点后，判断其是否存在右⼦树
            if(top->right != NULL)
                curr = top->right;
        }
        return ans;
    }
};

LeetCode 145. ⼆叉树的后序遍历

给定⼀个⼆叉树，返回它的后序遍历。

示例:

输⼊: [1,null,2,3]  
   1
    \
     2
    /
   3 
 
输出: [3,2,1]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

【思路】

1、前序遍历的过程是中左右。 2、将其转化成中右左。也就是压栈的过程中优先压⼊左⼦树，再压⼊右⼦树。 3、在弹栈的同时将此弹栈结点压⼊另⼀个栈，完成逆序。 4、对新栈中的元素直接顺序弹栈并输出。

【代码】

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), 
left(left), right(right) {}
 * };
 */
/*
//递归版
class Solution {
public:
    vector<int> ans;
    vector<int> preorderTraversal(TreeNode* root) {
        // 为空则直接返回
        if(root == NULL)
            return ans;
        preorderTraversal(root->left);
        preorderTraversal(root->right);
        ans.push_back(root->val);
        return ans;
    }
};
*/
//⾮递归版
class Solution {
public:
    std::vector<int> postorderTraversal(TreeNode* root) {
        std::vector<int> res;
        if (!root) return res;
        std::stack<TreeNode*> st1;
        std::stack<TreeNode*> st2;
        st1.push(root);
        // 栈⼀顺序存储
        while (!st1.empty()){
            TreeNode* node = st1.top();
            st1.pop();
            st2.push(node);
            if (node->left) st1.push(node->left);
            if (node->right) st1.push(node->right);
        }
        // 栈⼆直接输出
        while (!st2.empty()) {
            res.push_back(st2.top()->val);
            st2.pop();
        }
        return res;
    }
};

Previous87、十大排序算法及其时间和空间复杂度 Next89、设计模式

Last updated 2 years ago