美文网首页
[Leetcode]94. Binary Tree Inorde

[Leetcode]94. Binary Tree Inorde

作者: 木易yr | 来源:发表于2019-08-17 22:38 被阅读0次

    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?
    题意:二叉树的中序遍历,要求用迭代
    思路:使用到栈,将整棵树的最左边的一条链压入栈中,每次取出栈顶元素,如果它有右子树,则将右子树压入栈中。

    /**
     * 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) {
            vector<int>res;
            stack<TreeNode*> stk;
            auto p=root;
            while(p||stk.size())
            {
                while(p)//整颗子树的最左侧进栈
                {
                    stk.push(p);
                    p=p->left;
                }
                p=stk.top();
                stk.pop();
                res.push_back(p->val);
                p=p->right;
            }
            return res;
        }
    };
    

    给出递归写法

    /**
     * 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) {
            vector<int> result;
            inorder(root,result);
            return result;
        }
            void inorder(TreeNode* root,vector<int>& v){
                if(root!=nullptr){
                    inorder(root->left,v);
                    v.push_back(root->val);
                    inorder(root->right,v);
                }
            }
    };
    

    相关文章

      网友评论

          本文标题:[Leetcode]94. Binary Tree Inorde

          本文链接:https://www.haomeiwen.com/subject/eiiksctx.html