LeetCode 2415. Reverse Odd Levels of Binary Tree

https://leetcode.com/problems/reverse-odd-levels-of-binary-tree/description/

題目大意

給定 full BT，把基數 level 的節點左右翻轉
level 從 0 開始

思考

C++ 參考解答：

class Solution
{
public:
    TreeNode *reverseOddLevels(TreeNode *root)
    {
        dfs(root->left, root->right, true);
        return root;
    }

private:
    void dfs(TreeNode *lNode, TreeNode *rNode, bool isOddLevel)
    {
        if (!lNode)
            return;

        if (isOddLevel)
            swap(lNode->val, rNode->val);

        dfs(lNode->left, rNode->right, !isOddLevel);
        dfs(lNode->right, rNode->left, !isOddLevel);
    }
};

Go 參考解答：

Algo 1 BFS

怕有些人特別喜歡 BFS 這邊當練習寫了一下 BFS 的解法

func reverseOddLevels(root *TreeNode) *TreeNode {
	queue := []*TreeNode{root}

	for level := 0; len(queue) > 0; level++ {
		nodes := []*TreeNode{}
		sz := len(queue)

		for j := 0; j < sz; j++ {
			node := queue[0]
			queue = queue[1:]

			if level%2 == 1 {
				nodes = append(nodes, node)
			}

			if node.Left != nil {
				queue = append(queue, node.Left)
				queue = append(queue, node.Right)
			}
		}

		for l, r := 0, len(nodes)-1; l < r; {
			nodes[l].Val, nodes[r].Val = nodes[r].Val, nodes[l].Val
			l++
			r--
		}
	}

	return root
}

Algo 2 DFS

但以這題目來說 DFS ，用 DFS 還是比較好的
題目有說最多也就

$2^{14}$ 個 nodes，而且保證了其為 full，這樣的深度用 DFS 問題並不大

func reverseOddLevels(root *TreeNode) *TreeNode {
	dfs(root.Left, root.Right, true)
	return root
}

func dfs(lNode, rNode *TreeNode, isOddLevel bool) {
	if lNode == nil {
		return
	}

	if isOddLevel {
		lNode.Val, rNode.Val = rNode.Val, lNode.Val
	}

	dfs(lNode.Left, rNode.Right, !isOddLevel)
	dfs(lNode.Right, rNode.Left, !isOddLevel)
}