LinkedList to resolve it Space/Time O(N)


  • 0
    L
    public IList<IList<int>> ZigzagLevelOrder(TreeNode root) {
        IList<IList<int>> result = new List<IList<int>>();
        LinkedList<TreeNode> list = new LinkedList<TreeNode>();
        if(root != null) list.AddLast(root);
        bool toRight =true;
        while(list.Count != 0){
            LinkedList<TreeNode> newList = new LinkedList<TreeNode>();
            LinkedListNode<TreeNode> curFirst = list.First, curLast = list.Last;
            result.Add(new List<int>());
            while(curFirst != null){
                result[result.Count - 1].Add(curFirst.Value.val);
                if(toRight){
                    if(curLast.Value.right != null) newList.AddLast(curLast.Value.right);
                    if(curLast.Value.left != null) newList.AddLast(curLast.Value.left);
                }
                else{
                    if(curLast.Value.left != null) newList.AddLast(curLast.Value.left);
                    if(curLast.Value.right != null) newList.AddLast(curLast.Value.right);
                }
                curFirst = curFirst.Next; curLast = curLast.Previous;
            }
            list = newList; toRight = !toRight;
        }
        return result;
    }

Log in to reply
 

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