欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

94 二叉树的中序遍历

程序员文章站 2022-03-03 11:03:59
...

题目描述:
给定一个二叉树,返回它的中序 遍历。

示例:
输入: [1,null,2,3]
94 二叉树的中序遍历
输出: [1,3,2]
进阶: 递归算法很简单,你可以通过迭代算法完成吗?

方法1:递归
主要思路:
(1)正常的使用中序遍历即可;

/**
 * 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:
	//中序遍历
    void inorder(TreeNode* root,vector<int>& res){
        if(root==NULL)//正常的终止条件
            return ;
        inorder(root->left,res);
        res.push_back(root->val);
        inorder(root->right,res);
    }
	
    vector<int> inorderTraversal(TreeNode* root) {
    	//处理特殊的情形
        if(root==NULL)
            return vector<int>();
        vector<int> res;
        inorder(root,res);
        return res;
    }
};

方法2:使用栈实现迭代代码1
主要思路:
(1)使用栈实现,具体细节如代码所示;

/**
 * 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) {
    	//处理特殊的情形
        if(root==NULL)
            return vector<int>();
        stack<TreeNode*>st;
        st.push(root);//压入根节点
        TreeNode* tmp=NULL;
        vector<int> res;
        //栈非空,既未遍历完
        while(!st.empty()){
        	//将左结点压入到栈中
            while(st.top()->left)
                st.push(st.top()->left);
            //将结点弹出
            while(true){
                tmp=st.top();
                st.pop();
                res.push_back(tmp->val);
                if(tmp->right){//若右结点非空,则压入右结点,然后跳出弹出循环
                    st.push(tmp->right);
                    break;
                }
                if(st.empty())//若栈为空,则跳出弹出循环
                    break;
            }
        }
        return res;
    }
};

方法3:使用栈实现的迭代方法3
主要思路:
(1)使用栈实现的中序遍历,具体见代码细节;

/**
 * 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) {
        if(root==NULL)
            return vector<int>();
        stack<TreeNode*>st;
        vector<int> res;
        TreeNode* cur_node=root;
        //注意这里的终止条件和方法2的变化
        while(cur_node!=NULL||!st.empty()){
        	//将左结点都压入到栈中
            while(cur_node!=NULL){
                st.push(cur_node);
                cur_node=cur_node->left;
            }
            //弹出栈顶的元素
            cur_node=st.top();
            st.pop();
            res.push_back(cur_node->val);
            //处理右结点
            cur_node=cur_node->right;
        }
        return res;
    }
};
相关标签: LeetCode