Why every solution is using 2 while loops. The standard iterative solution shoule only has one while loop.


  • 3
    L
    public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> res = new ArrayList<Integer> ();
            if (root == null) return res;
            
            Stack<TreeNode> s = new Stack<TreeNode>();
            TreeNode n = root;
            
            while (n != null || !s.isEmpty()) {
                if  (n != null) {
                    s.push(n);
                    n = n.left;
                }
                else {
                    TreeNode l = s.pop();
                    res.add(l.val);
                    n = l.right;
                }
            }
            
            return res;
        }
    

  • 0
    L

    @leetcode_tester said in Why every solution is using 2 while loops. The standard iterative solution shoule only has one while loop.:

    public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> res = new ArrayList<Integer> ();
            if (root == null) return res;
            
            Stack<TreeNode> s = new Stack<TreeNode>();
            TreeNode n = root;
            
            while (n != null || !s.isEmpty()) {
                if  (n != null) {
                    s.push(n);
                    n = n.left;
                }
                else {
                    TreeNode l = s.pop();
                    res.add(l.val);
                    n = l.right;
                }
            }
            
            return res;
        }
    

    Push all the left nodes to stack, then pop up and push the right nodes.


  • 0
    Y
    /*
    I cannot agree more.
     */
    class Solution {
    public:
        vector<int> inorderTraversal(TreeNode* root) {
            vector<int> result;
            result.reserve(128);
            stack<TreeNode*> node_stack;
            while (root || !node_stack.empty()) {
                if (root) { //to visit does not have either left or right visited
                    node_stack.push(root);
                    root = root->left; //to visit
                } else { //in stack has left visited
                    root = node_stack.top();
                    node_stack.pop();
                    result.push_back(root->val);
                    root = root->right; //to visit
                }
            }
            return result;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.