98. Validate Binary Search Tree
題目描述：
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node''s key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
Example 1:
2
/ \
1 3
Input: [2,1,3]
Output: true
Example 2:
5
/ \
1 4
/ \
3 6
Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.
本題要求判斷一顆tree是否為二叉搜索樹脸秽。根據(jù)二叉搜索樹的定義，只要滿足任何一個節(jié)點的左節(jié)點的值小于該節(jié)點的值厢钧，右節(jié)點的值都大于該節(jié)點的值即可补鼻“送海回憶一下二叉樹的遍歷，根據(jù)二叉搜索樹的中序遍歷是有序的特點辛馆，在這里我們采用中序遍歷遍歷整棵樹，并判斷其值是否有序豁延，便可得到本題的解昙篙。
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isValidBST(root *TreeNode) bool {
if root == nil{
return true
}
var stack []*TreeNode
cur := root
var prev *TreeNode
for len(stack)>0 || cur!=nil{
if cur!=nil{
stack = append(stack,cur)
cur = cur.Left
}else{
cur = stack[len(stack)-1]
stack = stack[:len(stack)-1]
if prev!=nil &&prev.Val >= cur.Val{
return false
}
prev = cur
cur = cur.Right
}
}
return true
}
99. Recover Binary Search Tree
題目描述：
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Example 1:
Input: [1,3,null,null,2]
1
/
3
\
2
Output: [3,1,null,null,2]
3
/
1
\
2
Example 2:
Input: [3,1,4,null,null,2]
3
/ \
1 4
/
2
Output: [2,1,4,null,null,3]
2
/ \
1 4
/
3
Follow up:
A solution using O(n) space is pretty straight forward.
Could you devise a constant space solution?
本題依然是采用中序遍歷，主要是找到兩個錯序的節(jié)點诱咏，交換兩個節(jié)點的值即可苔可。O(n)空間的解法如下：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func recoverTree(root *TreeNode) {
cur := root
var pre,first,second *TreeNode
var stack []*TreeNode
for cur!=nil || len(stack)>0{
if cur != nil{
stack = append(stack,cur)
cur = cur.Left
}else{
cur = stack[len(stack)-1]
stack = stack[:len(stack)-1]
if pre != nil{
if pre.Val > cur.Val{
if first == nil{
first = pre
}
second = cur
}
}
pre = cur
cur = cur.Right
}
}
val := first.Val
first.Val = second.Val
second.Val = val
}
100. Same Tree
題目描述如下：
Given two binary trees, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical and the nodes have the same value.
Example 1:
Input: 1 1
/ \ / \
2 3 2 3
[1,2,3], [1,2,3]
Output: true
Example 2:
Input: 1 1
/ \
2 2
[1,2], [1,null,2]
Output: false
Example 3:
Input: 1 1
/ \ / \
2 1 1 2
[1,2,1], [1,1,2]
Output: false
本題要求判斷兩棵樹是否為相同的樹，采用遞歸判斷即可袋狞，解法如下：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isSameTree(p *TreeNode, q *TreeNode) bool {
if p == nil && q == nil{
return true
}else if p == nil || q == nil{
return false
}else
{
return p.Val == q.Val && isSameTree(p.Left,q.Left) && isSameTree(p.Right,q.Right)
}
}
101. Symmetric Tree
題目描述：
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree [1,2,2,3,4,4,3] is symmetric:
1
/ \
2 2
/ \ / \
3 4 4 3
But the following [1,2,2,null,3,null,3] is not:
1
/ \
2 2
\ \
3 3
Note:
Bonus points if you could solve it both recursively and iteratively.
本題與上題類似焚辅，也可以采取遞歸來判斷映屋。
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isSymmetric(root *TreeNode) bool {
if root == nil{
return true
}
return isSame(root.Left,root.Right)
}
func isSame(p,q *TreeNode) bool{
if p == nil && q == nil{
return true
}else if p==nil || q==nil{
return false
}else{
a := isSame(p.Left,q.Right)
b := isSame(p.Right,q.Left)
return p.Val == q.Val && a && b
}
}
102. Binary Tree Level Order Traversal
題目描述：
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
這里給出樹的層序遍歷的非遞歸實現(xiàn)，主要是要利用queue結構同蜻。
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func levelOrder(root *TreeNode) (ret [][]int) {
if root == nil{
return
}
que := []*TreeNode{root}
for len(que) > 0{
var res []int
size := len(que)
for i:=0;i < size;i++{
cur := que[0]
res = append(res,cur.Val)
que = que[1:]
if cur.Left!= nil{
que = append(que,cur.Left)
}
if cur.Right!=nil{
que = append(que,cur.Right)
}
}
ret = append(ret,res)
}
return
}
103. Binary Tree Zigzag Level Order Traversal
題目描述：
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
本題是樹的層序遍歷的一個應用棚点，要求每一層以不同的順序打印。這里只需要考慮不同層的打印順序與層數(shù)之間的關系即可湾蔓。
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func zigzagLevelOrder(root *TreeNode) (ret [][]int ){
if root == nil{
return
}
que := []*TreeNode{root}
isleft := true
for len(que) > 0{
size := len(que)
path := make([]int,size)
for i:=0;i<size;i++{
cur := que[0]
que = que[1:]
idx := i
if !isleft{
idx = size-1-i
}
path[idx] = cur.Val
if cur.Left!=nil{
que = append(que,cur.Left)
}
if cur.Right!=nil{
que = append(que,cur.Right)
}
}
ret = append(ret,path)
isleft = !isleft
}
return
}
104. Maximum Depth of Binary Tree
題目描述：
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Note: A leaf is a node with no children.
Example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its depth = 3.
本題要求二叉樹的最大高度瘫析。與大多數(shù)與樹有關的題目類似，主要采用遞歸方法來實現(xiàn)默责。
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func Max(x,y int) int{
if x > y{
return x
}else{
return y
}
}
func maxDepth(root *TreeNode) int {
if root == nil{
return 0
}
return Max(maxDepth(root.Left),maxDepth(root.Right))+1
}
