Geeks4Geeks - check-if-the-given-binary-tree-have-a-subtree-with-equal-no-of-1s-and-0s

https://www.geeksforgeeks.org/check-if-the-given-binary-tree-have-a-subtree-with-equal-no-of-1s-and-0s/

Given a Binary Tree having data at nodes as either 0's or 1's. The task is to find out whether there exists a subtree having an equal number of 1's and 0's.

1. change all 0 to -1 in the tree

2. create a sum tree, every node contains the sum of all nodes under it

3. iterate the tree and find whether there's a node having 0 sum

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

func findEqual01(head *TreeNode) bool {
	convert(head)
	sumTree(head)

	stack := []*TreeNode{}
	node := head
	for node != nil || len(stack) != 0 {
		for node != nil {
			if node.Val == 0 {
				return true
			}
			stack = append(stack, node.Left)
		}
		if len(stack) != 0 {
			node = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			stack = append(stack, node.Right)
		}
	}

	return false
}

func convert(head *TreeNode) {
	if head == nil {
		return
	}
	if head.Val == 0 {
		head.Val = -1
	}
	convert(head.Left)
	convert(head.Right)
}

func sumTree(head *TreeNode) int {
	if head == nil {
		return 0
	}
	oldVal := head.Val
	head.Val = sumTree(head.Left) + sumTree(head.Right)

	return head.Val + oldVal
}

def check_subtree head
  stack = []
  node = head
  while node != nil || stack.length != 0
    while node != nil
      return true if node.val == 0
      stack << node
      node = node.left
    end
    node = stack[stack.length-1]
    stack = stack[0..len(stack)-2]
    node = node.right
  end

  return false
end

def convert head
  if head == nil
    return
  end

  if head.val == 0
    head.val = -1
  end

  convert(head.left)
  convert(head.right)
end

def sum_tree head, sum
  if head == nil
    return 0
  end
  pre_sum = head.val
  head.val = sum_tree(head.left) + sum_tree(head.right)

  return head.val + pre_sum
end

• 相关文章
• 全局相关文章