🤔

備忘録集 LeetCode1457. Pseudo-Palindromic Paths in a Binary Tree,2分木,

2023/04/25に公開

立地

自分用の備忘録

3行まとめ

与えられた2分木を辿っていって、rootからleafまでの数値が回文になっているか判定（数値の順番は入れ替えていい）
dfsを書けるなら基本できる
O(N)時間でやるやつはテクい

前提

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

実装

普通のdfs

time:多分 $O(N^2)$ (データ総数 $N$ に対して葉の枚数が $O(N)$ 回、葉での処理が $O(N)$ 回)、space: $O(N)$

var stack Stack

func isPseudoPalindrom(stack Stack) bool {
	nums := make([]int, 10)
	allowed_odd := 0
	if len(stack)%2 == 1 {
		allowed_odd = 1
	}

	for _, v := range stack {
		nums[v]++
	}
	for _, v := range nums {
		if v%2 == 1 {
			allowed_odd--
		}
		if allowed_odd < 0 {
			return false
		}
	}
	return true
}

func pseudoPalindromicPaths(root *TreeNode) int {

	count := 0
	var dfs func(*TreeNode)

	dfs = func(root *TreeNode) {
		stack.PushBack(root.Val)
		defer stack.PopBack()

		if root.Left == nil && root.Right == nil {
			if isPseudoPalindrom(stack) {
				count++
			}
			return
		}
		if root.Right != nil {
			dfs(root.Right)
		}
		if root.Left != nil {
			dfs(root.Left)
		}
	}
	dfs(root)
	return count
}

工夫したdfs

time: $O(N)$ (データ総数 $N$ に対して葉の枚数が $O(N)$ 回、葉での処理が $O(N)$ 回)、space:多分 $O(1)$ （元ネタでは $O(K+H)$ になってたけどKとHが何か分からん。Kは1のビットの個数、Hは高さっぽい）

func pseudoPalindromicPaths_bit(root *TreeNode) int {
	ans := 0
	var dfs func(*TreeNode, int)

	dfs = func(root *TreeNode, count int) {
		count ^= 1 << root.Val
		if root.Left == nil && root.Right == nil {
			if count&(count-1) == 0 {
				ans++
			}
			return
		}

		if root.Right != nil {
			dfs(root.Right, count)
		}
		if root.Left != nil {
			dfs(root.Left, count)
		}
	}
	dfs(root, 0)
	return ans
}

立っているビットを1つ減らす

count&(count-1) == 0 がキモ。count&(count-1)はcountをビット列として見たとき、立っているビットを1つ減らした値を返す。今回はビットが0個か1個立っているときに回文となるので、立っているビットを1つ減らした値は0のはず。

何かしらの制約があるかも。多分unsigned intだけ
直感的には、以下。count&(count>>1) == 0はどうなのかな->だめらしい。どこかに0の桁があると1が2つ以上消える。

\begin{aligned} 00110 & \& (00110 - 1) \\ = 00110 & \& 00011 \\ = 00010 & \end{aligned}

記憶

自力でdfs書けたの初めてかもしれん。stackにpush,popするだけで基本はokなのを知らなかった。popすると破壊的な変更をしてる感じがしてアイデアが脳内で意識に浮かぶ前に却下されてる気がする。

参考文献

$O(n)$ の解法の元ネタ