二叉树的一些基础算法（先序，中序，后序，层次，深度，宽度，距离）

二叉树的一些基础算法

开始准备面试了，不定期更新一下更种各样的数据结构，记录一下吧。

1. 先序遍历，递归算法。
2. 中序遍历，递归算法。
3. 后序遍历，递归算法。
4. 先序遍历，非递归算法。
5. 中序遍历，非递归算法。
6. 后序遍历，非递归算法。
7. 二叉树的层次遍历。
8. 求二叉树的宽度
9. 求二叉树的深度
10. 求二叉树最远两个节点的距离。

0.二叉树节点

public class Node {
    public int value;
    public Node leftNode;
    public Node rightNode;
    
    //深度 用于求二叉树深度
    public int deep;
    
    //是否访问 用于后序遍历二叉树
    public int visit;
    
    //左右最远距离 用于求二叉树最远两个节点间距离
    public int leftLen;
    public int rightLen;
    
    public Node(int value) {
        this.value = value;
    }
    
    public Node(int value, Node left, Node right) {
        this.value = value;
        this.leftNode = left;
        this.rightNode = right;
    }

    @Override
    public String toString() {
        return "Node [value=" 
        + value + ", visit=" + visit + "]";
    }
}

1.先序遍历，递归算法

public static void preOrder(Node n) {
    if(n == null) {
        return;
    }
    System.out.println(n);
    preOrder(n.leftNode);
    preOrder(n.rightNode);
}

2.中序遍历，递归算法

public static void InOrder(Node n) {
    if(n == null) {
        return;
    }
    InOrder(n.leftNode);
    System.out.println(n);
    InOrder(n.rightNode);
}

3.中序遍历，递归算法

public static void postOrder(Node n) {
    if(n == null) {
        return;
    }   
    postOrder(n.leftNode);
    postOrder(n.rightNode);
    System.out.println(n);
}

4.先序遍历，非递归算法

非递归算法运用了栈的思想。

public static void preOrderStack(Node n) {
    Stack<Node> stack = new Stack<Node>();
    
    while(n != null || !stack.isEmpty()) {
        while(n != null) {
            System.out.println(n);
            stack.push(n);
            n = n.leftNode;
        }
        if(!stack.isEmpty()) {
            n = stack.pop();
            n = n.rightNode;
        }
        
    }
}

5.中序遍历，非递归算法

public static void inOrderStack(Node n) {
    Stack<Node> stack = new Stack<Node>();
    while(n != null || !stack.isEmpty()) {
        while(n != null) {
            stack.push(n);
            n = n.leftNode;
        }
        if(!stack.isEmpty()) {
            n = stack.pop();
            System.out.println(n);
            n = n.rightNode;
        }
    }
}

6.后序遍历，非递归算法

设置一个访问变量来判断节点的右子树是否已经访问。

public static void postOrderStack(Node n) {
    Stack<Node> stack = new Stack<Node>();
    while(n != null || !stack.isEmpty()) {
        while(n != null) {
            stack.push(n);
            n = n.leftNode;
        }
        while(!stack.empty() 
            && stack.peek().visit == 1) {
            System.out.println(stack.pop());
        }
        
        if(!stack.empty()) {
            n = stack.peek();
            n.visit = 1;
            n = n.rightNode;
        }
    }
}

7.二叉树的层次遍历

二叉树的层次遍历运用队列的思想。

public static void levelOrder(Node n) {
    if(n == null) {
        return;
    }
    Queue<Node> queue = new ArrayDeque<Node>();
    queue.add(n);
    
    while(queue.size() > 0) {
        n = queue.poll();
        System.out.println(n);
        if(n.leftNode != null) {
            queue.add(n.leftNode);
        }
        if(n.rightNode != null) {
            queue.add(n.rightNode);
        }
    }
}

8.求二叉树宽度

二叉树的宽度指的是，二叉树的每一层的节点数最多有多少。
思想与二叉树层次遍历相似。

public static int width(Node n) {
    Queue<Node> queue = new ArrayDeque<Node>();
    int maxWidth = 1;
    queue.add(n);
    
    while(queue.size() > 0) {
        int len = queue.size();
        while(len > 0) {
            n = queue.poll();
            len--;
            if(n.leftNode != null) {
                queue.add(n.leftNode);
            }
            if(n.rightNode != null) {
                queue.add(n.rightNode);
            }
        }
        maxWidth = Math.max(maxWidth, queue.size());
    }
    return maxWidth;
}

9.求二叉树深度

public static int deep(Node n) {
    if(n == null) {
        return 0;
    }
    int l = deep(n.leftNode);
    int r = deep(n.rightNode);
    if(l > r) {
        return l + 1;
    }
    return r + 1;
}

10.求二叉树最远两个节点的距离

求每个节点的左右长度，相加+1与最大距离相比。

public static int len(Node n, int maxValue) {
    if(n == null) {
        return 0;
    }
    if(n.leftNode == null) {
        n.leftLen = 0;
    }
    if(n.rightNode == null) {
        n.leftLen = 0;
    }
    if(n.leftNode != null) {
        len(n.leftNode, maxValue);
    }
    if(n.rightNode != null) {
        len(n.rightNode, maxValue);
    }
    
    if(n.leftNode != null) {
        if(n.leftNode.leftLen > n.leftNode.rightLen) {
            n.leftLen = n.leftNode.leftLen + 1;
        } else {
            n.leftLen = n.leftNode.rightLen + 1;
        }
    }
    
    if(n.rightNode != null) {
        if(n.rightNode.leftLen > n.rightNode.rightLen) {
            n.rightLen = n.rightNode.leftLen + 1;
        } else {
            n.rightLen = n.rightNode.rightLen + 1;
        }
    }
    
    if(n.leftLen + n.rightLen + 1 > maxValue) {
        maxValue = n.leftLen + n.rightLen + 1;
    }
    return maxValue;
}