跳过正文
  1. 数据结构与算法/

·152 字·1 分钟· loading
demo007x
作者
demo007x

检查给定的二叉树是否是和树
#

编写一个函数,如果给定的二叉树是 SumTree,则返回 true,否则返回 false。SumTree 是二叉树,其中节点的值等于其左子树和右子树中存在的节点之和。空树就是SumTree,空树的和可以认为是0。叶子节点也可以认为是SumTree。

以下是 SumTree 的示例。

         26 
        / \ 
      10   3 
     / \    \ 
    4   6    3

*方法一(简单)*

获取左子树和右子树中的节点之和。检查计算的总和是否等于根的数据。另外,递归检查左子树和右子树是否是 SumTree。

package main

import (
	"testing"
)

// 初始化树节点
func NewNode() *Node {
	return &Node{
		Data: 26,
		Left: &Node{
			Data: 10,
			Left: &Node{
				Data:  4,
				Left:  nil,
				Right: nil,
			},
			Right: &Node{
				Data:  6,
				Left:  nil,
				Right: nil,
			},
		},
		Right: &Node{
			Data: 3,
			Left: nil,
			Right: &Node{
				Data:  3,
				Left:  nil,
				Right: nil,
			},
		},
	}
}
// 判断是否是和树
func isSumTree(node *Node) bool {
	if node != nil {
		if node.Left != nil && node.Right != nil && node.Data == (node.Left.Data+node.Right.Data) {
			return true
		}

		if node.Left != nil {
			return isSumTree(node.Left)
		}
		if node.Right != nil {
			return isSumTree(node.Right)
		}
	}
	return false
}

func Test_isSumTree(t *testing.T) {
	if isSumTree(NewNode()) {
		t.Log("this is a sum tree")
	} else {
		t.Log("this not is a sum tree")
	}
}