【每日算法Day 26】二叉树基础1

内存中的树多数情况下都是二叉树的形式，其前序、中序、后序和层次遍历的方法以及遍历结果的特性是需要掌握的。在它们的基础上又会产生更复杂的问题。

二叉树遍历的递归写法很简单，只需要调整访问当前节点的值、递归调用左节点的遍历和递归调用左节点的遍历的顺序就可以了。

public void preOrder(TreeNode node){
    if (node != null) {
        System.out.print(node.val+" ");
        preOrder(node.left);
        preOrder(node.right);
    }
}
public void inOrder(TreeNode node){
    if (node != null) {
        inOrder(node.left);
        System.out.print(node.val+" ");
        inOrder(node.right);
    }
}
public void postOrder(TreeNode node){
    if (node != null) {
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.val+" ");
    }
}

然而，递归写法用到了系统的调用栈，一旦二叉树过大就可能造成调用栈溢出，所以非递归写法也需要掌握。非递归遍历主要使用自己的栈和循环来实现。

二叉树的层次遍历和其他三者不同，可以利用队列：

public void levelOrder(TreeNode node){
    if (node==null) return;
    Queue<TreeNode> q=new LinkedList<>();
    q.offer(node);
    while (!q.isEmpty()){
        TreeNode tmp=q.poll();
        System.out.print(tmp.val+" ");
        if (tmp.left!=null)
            q.offer(tmp.left);
        if (tmp.right!=null)
            q.offer(tmp.right);
    }
}

LeetCode 144. 二叉树的前序遍历 (opens new window)

前序遍历的非递归写法，核心思想是当节点不为空就访问当前节点的值，同时用栈保存访问过的父亲节点，再把指针指向当前节点的左孩子，就这样一直遍历直到左孩子为空。此时如果栈为空则遍历结束，当栈不为空时弹出栈顶（最后一次访问的节点），并对该节点的右孩子进行相同操作。

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> list=new ArrayList<>();
    if (root==null) return list;
    Deque<TreeNode> s= new LinkedList<>();
    while (true){
        while (root!=null){
            list.add(root.val);
            s.push(root);
            root=root.left;
        }
        if (s.size()==0)
            break;
        root=s.pop();
        root=root.right;
    }
    return list;
}

另一种前序遍历的非递归写法，思想是用栈保存将要访问的两个孩子节点，一开始将根节点入栈，接下来每次出栈顶的节点并访问，再依次压入该节点的右节点和左节点（不为空的话）。该方法与树的层次遍历思维类似。

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    if(root==null) return list;

    Deque<TreeNode> stack = new LinkedList<>();
    stack.push(root);
    while(stack.size()!=0){
        TreeNode node = stack.pop();
        list.add(node.val);
        if(node.right!=null)
            stack.push(node.right);
        if(node.left!=null)
            stack.push(node.left);
    }
    return list;
}

LeetCode 94. 二叉树的中序遍历 (opens new window)

中序遍历的非递归写法，与第一种前序遍历类似，同样是用栈保存访问过的节点，区别是将访问值的过程移到了每次出栈之后：

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list=new ArrayList<>();
    if (root==null) return list;
    Deque<TreeNode> s= new LinkedList<>();
    while (true){
        while (root!=null){
            s.push(root);
            root=root.left;
        }
        if (s.size()==0)
            break;
        root=s.pop();
        list.add(root.val);
        root=root.right;
    }
    return list;
}

LeetCode 145. 二叉树的后序遍历 (opens new window)

后序遍历的非递归写法，与第二种前序遍历类似，同样是用栈保存将要访问的两个孩子节点，区别是访问值的过程放在出栈后，而仅当栈顶元素的两个子节点都为空 或者 栈顶元素是在其两个子节点（不全部为空）出栈后来到栈顶 才将栈顶元素出栈，并更新最后一个出栈的元素，否则将该节点的右节点和左节点依次入栈。

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    if(root==null) return list;

    Deque<TreeNode> stack = new LinkedList<>();
    stack.push(root);
    TreeNode curNode,lastPopedNode=null;
    while(stack.size()!=0){
        curNode=stack.peek();
        if((curNode.left==null&&curNode.right==null)||
           (lastPopedNode!=null&&(lastPopedNode==curNode.left||lastPopedNode==curNode.right))){
                list.add(stack.pop().val);
                lastPopedNode=curNode;
        }else{
            if(curNode.right!=null)
                stack.push(curNode.right);
            if(curNode.left!=null)
                stack.push(curNode.left);
        }
    }
    return list;
}