树的前中后序遍历-递归实现：

public class TreeTraversal {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int value) {
            this.value = value;
        }
    }

    // 二叉树的递归遍历
    public static void preOrderRecursive(Node head) {
        if (head == null) {
            return;
        }

        System.out.print(head.value + " ");
        preOrderRecursive(head.left);
        preOrderRecursive(head.right);
    }

    public static void inOrderRecursive(Node head) {
        if (head == null) {
            return;
        }

        inOrderRecursive(head.left);
        System.out.print(head.value + " ");
        inOrderRecursive(head.right);
    }

    public static void postOrderRecursive(Node head) {
        if (head == null) {
            return;
        }

        postOrderRecursive(head.left);
        postOrderRecursive(head.right);
        System.out.print(head.value + " ");
    }

}

树的前中后序遍历-非递归实现：
import java.util.Stack;


public class TreeTraversal {
    public static class Node {
        public int value;
        public Node left;
        public Node right;
        public Node(int value) {
            this.value = value;
        }
    }
    // 二叉树的非递归遍历
    public static void preOrder(Node head) {
        System.out.print("pre-order: ");
        if (head == null) {
            return;
        }
        Stack<Node> s = new Stack<>();
        s.push(head);
        while (!s.isEmpty()) {
            head = s.pop();
            System.out.print(head.value + " ");
            if (head.right != null) {
                s.push(head.right);
            }

            if (head.left != null) {
                s.push(head.left);
            }
        }
        System.out.println();
    }

    public static void inOrder(Node head) {
        System.out.print("in-order: ");
        if (head == null) {
            return;
        }
        Stack<Node> s = new Stack<>();
        while (!s.isEmpty() || head != null) {
            if (head != null) {
                s.push(head);
                head = head.left;
            } else {
                head = s.pop();
                System.out.print(head.value + " ");
                head = head.right;
            }
        }
        System.out.println();
    }

    public static void postOrder(Node head) {
        System.out.print("pos-order: ");
        if (head == null) {
            return;
        }

        Stack<Node> tmp = new Stack<>();
        Stack<Node> s = new Stack<>();

        tmp.push(head);
        while(!tmp.isEmpty()) {
            head = tmp.pop();
            s.push(head);

            if (head.left != null) {
                tmp.push(head.left);
            }

            if (head.right != null) {
                tmp.push(head.right);
            }
        }

        while (!s.isEmpty()) {
            System.out.print(s.pop().value + " ");
        }

        System.out.println();
    }
}

今天的题目很适合递归实现，当然递归公式离代码实现还是存在一定距离。
1.翻转二叉树（T）｛
当T为Null时则返回；
翻转二叉树（T的左子树）；
翻转二叉树（T的右子树）；
若T不为叶节点，则交换T的左右子树位置；
｝

2.最大深度（T）｛
当T为Null时，return 0；
return Max（最大深度（T左子树）+1，最大深度（T右子树）+1）；
｝
函数返回值即为最大深度。

3.验证二叉查找树（T，&最大值，&最小值）｛
当T为Null时，return true；
当T为叶节点时，最小值=最大值=当前节点，返回true；
左最大值=左最小值=T的值；
验证二叉查找树（T的左子树，&左最大值，&左最小值）；
右最大值=右最小值=T的值；
验证（T的右子树，&右最大值，&右最小值）；
T的值小于等于右最小值，并且大于等于左最大值时，最大值=右最大值，最小值=左最小值，之后返回true，否则返回false并结束。
｝
函数最终返回true则验证成功。

4.计算路径和（T，sum）｛
若T为Null返回false；
若T是叶节点，如果sum+T的值=目标值则返回true并结束，否则返回false；
计算路径和（T的左子树，sum+T的值）；
计算路径和（T的右子树，sum+T的值）；
｝
计算路径和（T，0）返回true时则存在于目标值相同的路径之和；

二叉树的最大深度 go 语言实现
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 * Val int
 * Left *TreeNode
 * Right *TreeNode
 * }
 */
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    
    leftDepth :=0
    rightDepth :=0
    if root.Left != nil {
        leftDepth = maxDepth(root.Left)
    }
    
    if root.Right != nil {
        rightDepth = maxDepth(root.Right)
    }
    
    if leftDepth >= rightDepth {
        return leftDepth + 1
    } else {
        return rightDepth + 1
    }
}

// 翻转二叉树
public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return root;
        }
        TreeNode node = root;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(node);
        while(!queue.isEmpty()){
            node = queue.poll();
            TreeNode tempNode = node.left;
            node.left = node.right;
            node.right = tempNode;
            if(node.left != null){
                queue.offer(node.left);
            }
            if(node.right != null){
                queue.offer(node.right);
            }
        }
        return root;
    }
// 二叉树的最大深度
public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right))+1;
    }
// 验证二叉查找树
public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        TreeNode preNode = null;
        while(node != null || !stack.isEmpty()){
            stack.push(node);
            node = node.left;
            while(node == null && !stack.isEmpty()){
                node = stack.pop();
                if(preNode != null){
                    if(preNode.val >= node.val){
                        return false;
                    }
                }
                preNode = node;
                node = node.right;
            }
        }
        return true;
    }
// 路径总和
public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        return hasPathSum(root, root.val, sum);
    }

    public boolean hasPathSum(TreeNode root, int tmp, int sum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            return tmp == sum;
        }
        if (root.left == null) {
            return hasPathSum(root.right, root.right.val + tmp, sum);
        }
        if (root.right == null) {
            return hasPathSum(root.left, root.left.val + tmp, sum);
        }
        return hasPathSum(root.left, root.left.val + tmp, sum) ||
                hasPathSum(root.right, root.right.val + tmp, sum);
    }

#验证二叉搜索树
def isValidBST(self, root: TreeNode) -> bool:
        def inorderTraversal(root):
            if root == None:
                return []
            res = []
            res += inorderTraversal(root.left)
            res.append(root.val)
            res += inorderTraversal(root.right)
            return res
 
        res = inorderTraversal(root)
        if res != sorted(list(set(res))): return False
        return True

#实现小顶堆
def makeSmallHeap(array):
    for i in range(int(len(array)/2) , -1 , -1):
        makeHeap(array , i , len(array))
def makeHeap(array , i ,N):
    while 2*i+1 < N:
        child = 2*i+1
        if child != N-1 and array[child] > array[child+1]:
            child+=1
        if array[child] < array[i]:
            temp = array[child]
            array[child] = array[i]
            array[i] = temp
            i = child
        else:
            break

#实现大顶堆
def makeBigHeap(array):
    for i in range(int(len(array)/2) , -1 , -1):
        makeHeap(array , i , len(array))
def makeHeap(array , i ,N):
    while 2*i+1 < N:
        child = 2*i+1
        if child != N-1 and array[child] < array[child+1]:
            child+=1
        if array[child] > array[i]:
            temp = array[child]
            array[child] = array[i]
            array[i] = temp
            i = child
        else:
            break

#堆排序
import random
import time

def Array(n):
    a = []
    for i in range(n):
        a.append(random.randint(0 , n))
    return a

def makeHeap(array , i ,N):
    while 2*i+1 < N:
        child = 2*i+1
        if child != N-1 and array[child] < array[child+1]:
            child+=1
        if array[child] > array[i]:
            temp = array[child]
            array[child] = array[i]
            array[i] = temp
            i = child
        else:
            break
def heapSort():
    array = Array(100)
    for i in range(int(len(array)/2) , -1 , -1):
        makeHeap(array , i , len(array))
    for i in range(len(array)-1 , -1 , -1):
        temp = array[0]
        array[0] = array[i]
        array[i] = temp
        makeHeap(array , 0 , i)
    print(array)

路径总和: 使用回溯法, 遍历每一条 root->leaf 的路线是否满足在和为 sum, 可以使用减枝操作

二叉树深度 = 左右子树中深度最大者 + 1

验证二叉搜索树:
1. 遍历每一个结点, 若都满足, 当前结点大于左子树中的最大值, 小于右子树中的最小值, 则说明为二叉搜索树
2. 中序遍历二叉搜索树, 若序列递增, 则说明为二叉搜索树

#二叉树前中后序及层次遍历非递归版本
class Tree:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

#----前序----
def preOrder(Tree T):
    if T is None:
        return []
    list1 = []
    list2 = []
    list1.append(T)
    while len(list1) > 0:
        t = list1.pop()
        list2.append(t)
        if t.right not None:
            list1.append(t.right)
        if t.left not None:
            list1.append(t.left)
    return list2

#----中序----
def inOrder(Tree T):
    if T is None:
        return []
    list1 = []
    list2 = []
    while T or len(list1)>0 :
        if T :
            list1.append(T)
            T = T.left
        else:
            T = list1.pop()
            list2.append(T)
            T = T.right
    return list2

#----后序----
def postOrder(Tree T):
    if T is None:
        return []
    list1 = []
    list2 = []
    list1.append(T)
    while len(list1)>0 :
        t = list1.pop()
        list2.append(t)
        if t.left not None:
            list1.append(t.left)
        if t.right not None:
            list1.append(t.right)
    return list2[::-1]

#----层次-----
def levelOrder():
    if T is None:
        return []
    list1 = []
    list2 = []
    list1.append(T)
    while len(list1)>0 :
        t = list1[0]
        del list1[0]
        list2.append(t)
        if t.left not None:
            list1.append(t.left)
        if t.right not None:
            list1.append(t.right)
    return list2

java实现二叉树前序、中序、后序和层次遍历
代码如下：
package tree;

import java.util.LinkedList;
import java.util.Queue;

public class BinaryTree {
    
    private Node root = null;
    
    public static class Node {
        
        private String data;
        private Node left;
        private Node right;
        
        public Node(String data, Node left, Node right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }
    }
    
    public void preOrder(Node root) {
        if (null == root) {
            return ;
        }
        System.out.print(root.data + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
    
    public void inOrder(Node root) {
        if (null == root) {
            return ;
        }
        inOrder(root.left);
        System.out.print(root.data + " ");
        inOrder(root.right);
    }
    
    public void postOrder(Node root) {
        if (null == root) {
            return ;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.data + " ");
    }
    
    public void traverseByLayer(Node root) {
        if (null == root) {
            return ;
        }
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node pNode = queue.peek();
            System.out.print(pNode.data + " ");
            queue.poll();
            if (root.left != null) {
                queue.add(root.left);
            }
            if (root.right != null) {
                queue.add(root.right);
            }
        }
    }
}

Path Sum（路径总和）go 语言实现
func hasPathSum(root *TreeNode, sum int) bool {

    if root==nil{
        return false
    }
    if root.Left==nil && root.Right==nil{
        if root.Val==sum{
            return true
        }else{
            return false
        }

    }
    left:=false
    if root.Left!=nil{
        left=hasPathSum(root.Left,sum-root.Val)
    }
    right:=false
    if root.Right!=nil{
        right=hasPathSum(root.Right,sum-root.Val)
    }
    return left || right
}

Validate Binary Search Tree（验证二叉查找数） go语言实现

func isValidBST(root *TreeNode) bool {

    if root==nil{
        return true
    }
    less:=true
    more:=true
    if root.Left!=nil{
        less=JudgeLess(root.Left,root.Val)
    }
    if root.Right!=nil{
        more=JudgeMore(root.Right,root.Val)
    }
    if ! (less && more){
        return false
    }else{
        return isValidBST(root.Left) && isValidBST(root.Right)
    }
}

func JudgeLess(root *TreeNode,num int) bool{

    if root.Val>=num{
        return false
    }
    if root.Left!=nil && root.Right!=nil{
        return JudgeLess(root.Left,num) && JudgeLess(root.Right,num)
    }else if root.Left!=nil{
        return JudgeLess(root.Left,num)
    }else if root.Right!=nil{
        return JudgeLess(root.Right,num)
    }else{
        return true
    }
}

func JudgeMore(root *TreeNode,num int) bool{
    if root.Val<=num{
        return false
    }
    if root.Left!=nil && root.Right!=nil{
        return JudgeMore(root.Left,num) && JudgeMore(root.Right,num)
    }else if root.Left!=nil{
        return JudgeMore(root.Left,num)
    }else if root.Right!=nil{
        return JudgeMore(root.Right,num)
    }else{
        return true
    }
}

Invert Binary Tree（翻转二叉树） go 语言实现
func invertTree(root *TreeNode) *TreeNode {
    if root==nil{
        return root
    }
    temp:=root.Left
    root.Left=root.Right
    root.Right=temp
    invertTree(root.Left)
    invertTree(root.Right)
    return root
}