Ltd的算法大抄·二叉树II

// 遍历思想
func maxDepth(root *TreeNode) int {
	max, dep := 0, 0
	var traverse func(node *TreeNode)
	traverse = func(node *TreeNode) {
		if node == nil {
			return
		}
		//进入一个节点
		dep++
		//若是叶子节点就计算比较最大深度
		if node.Left == nil && node.Right == nil && dep > max {
			max = dep
		}
		//继续左右遍历
		traverse(node.Left)
		traverse(node.Right)
		dep--
	}
	traverse(root)
	return max
}

// 分解问题
func maxDepth1(root *TreeNode) int {
	if root == nil {
		return 0
	}
	//分别求解
	leftMax := maxDepth1(root.Left)
	rightMax := maxDepth1(root.Right)
	//通过子树的最大值求
	if leftMax > rightMax {
		return leftMax + 1
	} else {
		return rightMax + 1
	}
}

func diameterOfBinaryTree(root *TreeNode) (max int) {
	diameter := 0
	//函数求的是最大深度，但直径可以通过深度来计算
	depMax(root, &diameter)
	return diameter
}

func depMax(node *TreeNode, diameter *int) int {
	if node == nil {
		return 0
	}
	//求左右子树的最大深度
	leftMax := depMax(node.Left, diameter)
	rightMax := depMax(node.Right, diameter)
	//通过深度求当前节点的直径
	diameterTmp := leftMax + rightMax
	//获取全局最大直径
	if diameterTmp > *diameter {
		*diameter = diameterTmp
	}
	//返回最大的深度
	if leftMax > rightMax {
		return leftMax + 1
	} else {
		return rightMax + 1
	}
}

func levelOrder(root *TreeNode) (ans [][]int) {
	if root == nil {
		return ans
	}
	//用来存放每一层的所有节点，其实相当于一个队列
	q := []*TreeNode{root}

	for len(q) > 0 {
		//获取当前层的大小固定的值
		levelSize := len(q)
		//用来存放这一层的所有节点值
		var thisLevel []int
		//遍历完这一层里的所有节点
		for i := 0; i < levelSize; i++ {
			cur := q[0]
			thisLevel = append(thisLevel, cur.Val)
			//将左右子树放进q中等待下一层遍历
			if cur.Left != nil {
				q = append(q, cur.Left)
			}
			if cur.Right != nil {
				q = append(q, cur.Right)
			}
			//删除这个节点，相当于出队
			q = q[1:]
		}
		//一层遍历完了加入结果中
		ans = append(ans, thisLevel)
	}
	return ans
}

func levelOrderBottom(root *TreeNode) (ans [][]int) {
	if root == nil {
		return ans
	}
	//用来存放每一层的所有节点，相当于一个队列
	q := []*TreeNode{root}

	for len(q) > 0 {
		//获取当前层固定的值
		levelSize := len(q)
		//用来存放这一层的所有节点值
		var thisLevel []int
		//遍历完这一层里的所有节点
		for i := 0; i < levelSize; i++ {
			cur := q[0]
			thisLevel = append(thisLevel, cur.Val)
			//将左右子树放进q中等待下一层遍历
			if cur.Left != nil {
				q = append(q, cur.Left)
			}
			if cur.Right != nil {
				q = append(q, cur.Right)
			}
			//删除这个节点，相当于出队
			q = q[1:]
		}
		//一层遍历完了加入结果的前面就是从下往上的顺序了
		ans = append([][]int{thisLevel}, ans...)
	}
	return ans
}

func connect(root *Node) *Node {
	//存在用例
	if root == nil {
		return nil
	}
	traverse1(root.Left, root.Right)
	return root
}
func traverse1(node1, node2 *Node) {
    //完美二叉树似乎判断一个也够了
	if node1 == nil || node2 == nil {
		return
	}
	//连接当前两个节点
	node1.Next = node2
	//连接相同父节点的两子节点
	traverse1(node1.Left, node1.Right)
	traverse1(node2.Left, node2.Right)
	//连接不同父节点的两个子节点
	traverse1(node1.Right, node2.Left)
}

//遍历的思想
func connect(root *Node) *Node {
	//存在用例
	if root == nil {
		return nil
	}
	traverse1(root.Left, root.Right)
	return root
}
func traverse1(node1, node2 *Node) {
	if node1 == nil || node2 == nil {
		return
	}
	//连接当前两个节点
	node1.Next = node2
	//连接相同父节点的两子节点
	traverse1(node1.Left, node1.Right)
	traverse1(node2.Left, node2.Right)
	//连接不同父节点的两个子节点
	traverse1(node1.Right, node2.Left)
}

// 分解：先将最底层的节点拉伸为直线，再不断向上拉伸
func flatten(root *TreeNode) {
	if root == nil {
		return
	}
	flatten(root.Left)
	flatten(root.Right)
	//后序位置，意味着底层的节点已经交换完了，只需考虑当前层的操作
	//为了更直观选择先保存下之前的节点
	left := root.Left
	right := root.Right
	//将左节点放到右节点的位置
	root.Right = left
	//置空左节点
	root.Left = nil
	p := root
	//到达当前右边的最末端
	for p.Right != nil {
		p = p.Right
	}
	//将之前的right放到现在的节点的最右端
	p.Right = right
}