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是否为二叉搜索树。根据二叉搜索树的定义，只要满足任何一个节点的左节点的值小于该节点的值，右节点的值都大于该节点的值即可。回忆一下二叉树的遍历，根据二叉搜索树的中序遍历是有序的特点，在这里我们采用中序遍历遍历整棵树，并判断其值是否有序，便可得到本题的解。

/**
 * 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?

本题依然是采用中序遍历，主要是找到两个错序的节点，交换两个节点的值即可。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]
]

这里给出树的层序遍历的非递归实现，主要是要利用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]
]

本题是树的层序遍历的一个应用，要求每一层以不同的顺序打印。这里只需要考虑不同层的打印顺序与层数之间的关系即可。

/**
 * 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.

本题要求二叉树的最大高度。与大多数与树有关的题目类似，主要采用递归方法来实现。

/**
 * 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
}