Leetcode 94. 二叉树的中序遍历

1.问题描述

给定一个二叉树，返回它的中序遍历。

示例:

输入: [1,null,2,3]

   1

    \

     2

    /

   3

输出: [1,3,2]

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

2.解法一：递归

中序遍历：L--N--R (左--根--右)

class Solution {

public:

    vector<int> inorderTraversal(TreeNode* root) {

        if(root){

            inorderTraversal(root->left);  //左

            res.push_back(root->val);     //根

            inorderTraversal(root->right);//右

        }

            return res;

    }

private:

    vector<int> res;

};

3.递归与迭代的区别

递归：A反复调用A自身
迭代：A不停调用B （B是利用变量的原值推算出变量的一个新值）

注意：
（1）递归中一定有迭代,但是迭代中不一定有递归；
（2）能使用迭代尽量使用迭代

4.解法二：非递归（栈）

/**

 * 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> inorderTraversal(TreeNode* root) {

        stack<TreeNode*> s;

        //s.push(root);

        TreeNode* cur = root;//

    //L--N--R

    while(cur || !s.empty())

        if(cur){

            s.push(cur);

            cur = cur->left; //先走到最左子树

        }

        else{

            res.push_back(s.top()->val);

            cur = s.top()->right;

            s.pop();

        }

        return res;

    }

private:

    vector<int> res;

};

5.解法三：线索二叉树（不用递归不用栈）

class Solution {

public:

    vector<int> inorderTraversal(TreeNode* root) {

        //判空

        if (!root) return res;

        TreeNode *cur, *pre;//当前指针cur，前驱指针pre

        cur = root;

        //二叉树线索化&中序遍历

        while (cur){

            //左子树为空时

            if (!cur->left){

                res.push_back(cur->val);

                cur = cur->right;

            }

            //左子树不空时

            else{

                pre = cur->left;

                while (pre->right && pre->right != cur)

                {

                    pre = pre->right;

                }

                //pre->right为空

                if (!pre->right){

                    pre->right = cur;

                    cur = cur->left;

                }

                //pre->right不空

                else{

                    pre->right = NULL;

                    res.push_back(cur->val);

                    cur = cur->right;

                }

            }

        }

        return res;

    }

//数据的封装

private:

    vector<int> res;

};

参考资料：

1.https://blog.csdn.net/swliao/article/details/5337896 递归与迭代的区别

2.https://www.cnblogs.com/ariel-dreamland/p/9159638.html

巴特西

Leetcode 94. 二叉树的中序遍历

1.问题描述

2.解法一：递归

3.递归与迭代的区别

4.解法二：非递归（栈）

5.解法三：线索二叉树（不用递归不用栈）

最新文章

热门文章