题解 | #二叉树的中序遍历#

package main

import "fmt"

/**
 * Created by Chris on 2021/8/1.
 */
 
type TreeNode struct{
	Val int
	Left *TreeNode
	Right *TreeNode
}

/**
解法一：dfs
 */
func sumNumbers( root *TreeNode ) int {
	return dfs(0, root)
}

func dfs(currentSum int, node *TreeNode) int {
	if node == nil{
		return 0
	}
	var sum = currentSum * 10 + node.Val
	if node.Left == nil && node.Right == nil{
		return sum
	} else{
		return dfs(sum, node.Left) + dfs(sum, node.Right)
	}
}

/**
解法二：bfs
使用切片来模拟Java中的Queue队列
 */
type pair struct{
	//存储当前节点
	node *TreeNode
	//存储当前路的数值
	num int
}
func sumNumbers1( root *TreeNode ) int {
	if root == nil{
		return 0
	}
	var res int = 0
	//初始化队列
	var queue = []pair{{root, root.Val}}
	//开始读取队列中的数据
	for ;len(queue) > 0;{
		var tempNode = queue[0]
		queue = queue[1:]
		var leftNode = tempNode.node.Left
		var rightNode = tempNode.node.Right
		var num = tempNode.num
		if leftNode == nil && rightNode == nil{
			res += num
		} else{
			if leftNode != nil{
				queue = append(queue, pair{leftNode, num * 10 + leftNode.Val})
			}
			if rightNode != nil{
				queue = append(queue, pair{rightNode, num * 10 + rightNode.Val})
			}
		}
	}
	return res
}

/**
答案： 13 + 12 = 25
 */
func main(){
	var node1 = &TreeNode{1, nil, nil}
	var node2 = &TreeNode{2, nil, nil}
	var node3 = &TreeNode{3, nil, nil}
	//var node4 = &TreeNode{4, nil, nil}

	node1.Left = node2
	node1.Right = node3
	//node3.Right = node4

	var res = sumNumbers1(node1)
	fmt.Println(res)
}