JavaScript, no extra space non-recursion inorder traverse


  • 0
    P

    Code is kind of ugly...

    var findMode = function(root) {
        var res = [];
        if(!root) {
            return res;
        }
        var tem;
        var temCount = 0;
        var maxCount = 0;
        var pNode = root;
        
    
        while(pNode!==null) {
            var pLeft = pNode.left;
            if(pLeft) {
                while(pLeft.right!==null && pLeft.right!==pNode) {
                    pLeft = pLeft.right;
                }
                if(pLeft.right===null) {
                    pLeft.right = pNode;
                    pNode = pNode.left;
                    continue;
                } else {
                    pLeft.right = null;
                }
            }
    
            if(pNode.val===tem) {
                temCount++;
            } else {
                if(tem!==undefined) {
                    if(temCount>maxCount) {
                        res.length = 0;
                        maxCount = temCount;
                        res.push(tem);
                    }
                    else if(temCount===maxCount) {
                        res.push(tem);
                    }
                }
                tem = pNode.val;
                temCount = 0;
            }
            pNode = pNode.right;
        }
        if(temCount>maxCount) {
            res.length = 0;
            maxCount = temCount;
            res.push(tem);
        }
        else if(temCount===maxCount) {
            res.push(tem);
        }
        return res;
    };
    

  • 0

    @Philic similar idea here, a little more concise

    
        public int[] FindMode(TreeNode root) 
        {
            if (root == null) return new int[0];
            
            TreeNode node = root;
            Stack<TreeNode> stack = new Stack<TreeNode>();
            
            int currVal = root.val - 1;
            int currCnt = 0;
            int maxCnt = 0;
            HashSet<int> maxVals = new HashSet<int>();
            
            while (node != null || stack.Count > 0)
            {
                if (node != null)
                {
                    stack.Push(node);
                    node = node.left;
                }
                else
                {
                    TreeNode x = stack.Pop();
                    
                    // --------------------------------------------
                    // visit
                    if (x.val != currVal) currCnt = 0;
                    
                    currCnt++;
                    currVal = x.val;
                    
                    if (currCnt == maxCnt)
                    {
                        maxVals.Add(currVal);
                    }
                    else if (currCnt > maxCnt)
                    {
                        maxCnt = currCnt;
                        maxVals.Clear();
                        maxVals.Add(currVal);
                    }
                    // end visit
                    // --------------------------------------------
                    
                    // go right
                    node = x.right;
                }
            }
            
            return maxVals.ToArray();
        }
    

Log in to reply
 

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