Flatten Binary Tree to Linked List II

Another problem where you either have to flatten the binary tree into a linked list, or push it into a queue. I decided to do the former - it is easy to have a list of list of nodes, where each index is the level of the tree, and each list is the list of nodes in that level. If you do a pre-order depth-first search (DFS) you can accomplish that.

Second part of the problem is the calculation based on the given rules. Just go thru the flatten list, and to the list of nodes, and process based on the rules. If you look at the code down below, it achieves a high degree of symmetry which is usually a trademark when operating with trees. Cheers, ACC.

Zigzag Level Sum of Binary Tree - LeetCode

You are given the root of a binary tree.

Traverse the tree level by level using a zigzag pattern:

• At odd-numbered levels (1-indexed), traverse nodes from left to right.
• At even-numbered levels, traverse nodes from right to left.

While traversing a level in the specified direction, process nodes in order and stop immediately before the first node that violates the condition:

• At odd levels: the node does not have a left child.
• At even levels: the node does not have a right child.

Only the nodes processed before this stopping condition contribute to the level sum.

Return an integer array ans where ans[i] is the sum of the node values that are processed at level i + 1.

 

Example 1:

Input: root = [5,2,8,1,null,9,6]

Output: [5,8,0]

Explanation:

​​​​​​​

• At level 1, nodes are processed left to right. Node 5 is included, thus ans[0] = 5.
• At level 2, nodes are processed right to left. Node 8 is included, but node 2 lacks a right child, so processing stops, thus ans[1] = 8.
• At level 3, nodes are processed left to right. The first node 1 lacks a left child, so no nodes are included, and ans[2] = 0.
• Thus, ans = [5, 8, 0].

Example 2:

Input: root = [1,2,3,4,5,null,7]

Output: [1,5,0]

Explanation:

• At level 1, nodes are processed left to right. Node 1 is included, thus ans[0] = 1.
• At level 2, nodes are processed right to left. Nodes 3 and 2 are included since both have right children, thus ans[1] = 3 + 2 = 5.
• At level 3, nodes are processed left to right. The first node 4 lacks a left child, so no nodes are included, and ans[2] = 0.
• Thus, ans = [1, 5, 0].

 

Constraints:

• The number of nodes in the tree is in the range [1, 105].
• -105 <= Node.val <= 105

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public IList ZigzagLevelSum(TreeNode root)
    {
        List> treeList = new List>();
        FlattenBinaryTree(root, 0, treeList);

        long[] retVal = ProcessFlatBinaryTree(treeList);

        return retVal.ToList();
    }

    private void FlattenBinaryTree(TreeNode node,
                           int currentIndex,
                           List> treeList)
    {
        if (node == null) return;

        if (currentIndex >= treeList.Count)
            treeList.Add(new List());

        treeList[currentIndex].Add(node);

        FlattenBinaryTree(node.left, currentIndex + 1, treeList); ;
        FlattenBinaryTree(node.right, currentIndex + 1, treeList); ;
    }

    private long[] ProcessFlatBinaryTree(List> treeList)
    {
        long[] retVal = new long[treeList.Count];

        for (int index = 0; index < treeList.Count; index++)
        {
            if ((index + 1) % 2 == 1)
            {
                for (int i = 0; i < treeList[index].Count; i++)
                {
                    if (treeList[index][i].left == null) break;
                    retVal[index] += treeList[index][i].val;
                }
            }
            else
            {
                for (int i = treeList[index].Count - 1; i >= 0; i--)
                {
                    if (treeList[index][i].right == null) break;
                    retVal[index] += treeList[index][i].val;
                }
            }
        }

        return retVal;
    }
}