第六周 2020 年 11 月 30 ~ 2020 年 12 月 06

Algorithm/Tip:

二叉树的循环遍历

二叉树的层序遍历：

二叉树的层序遍历，一般使用队列或者栈来实现。
先使用栈或者队列存储第一层的节点，然后在下次循环时取出上一层的节点，并存储下一层的节点。如何循环往复，循环到最后一层。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public void levelTraverse(TreeNode root){
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    while(!q.isEmpty()){
        int size = q.size();
        for(int i = 0; i < size; ++i){
            // 获取到每个 node，在得到 node 后，可由根据需求进行其他操作
            TreeNode node = q.poll();
            if(node.left != null){
                q.offer(node.left);
            }
            if(node.right != null){
                q.offer(node.right);
            }
        }
        // 完成一层的遍历，在这里可以计算其高度，也可以保存各层的节点
    }     
}

二叉树的前序遍历：

二叉树的循环中的前序遍历，个人了解到一版有两种方式，但是其都是使用栈实现的。
循环方式的前序遍历，就是先按照 根节点->左节点 这一条线一直遍历，并将当前节点保存到栈中，当遍历到左叶节点之后，然后在往上回溯，继续遍历遇到的右节点。

使用栈实现前序遍历：

前序遍历的特点是：根节点->左节点->右节点 。
栈的特点是先入后出，所以入栈的顺序应该：根节点->右节点->左节点；

void preorder(TreeNode root){
    if(root == null){
        return;
    }
    Deque<TreeNode> stack = new LinkedList<>();
    // 根节点 入栈 
    stack.push(root);
    while(!stack.isEmpty()){
        // 在循环中首先出栈的就是 根节点，然后依次入栈 右节点-> 左节点
        // 下次循环，弹出上次入栈的节点，由于入栈的顺序是 右节点->左节点；
        // 那么出栈的顺序就是：左节点->右节点
        TreeNode node = stack.pop();
        System.out.println(node == null ? "null" : node.val);
        // 右节点 入栈 
        if(node.right != null){
            stack.push(node.right);
        }
        // 左节点 入栈 
        if(node.left != null){
            stack.push(node.left);
        }
    }
}

另一种方式：

    void preorder(TreeNode root){
        if(root == null){
            return;
        }
        // 使用双端队列来实现栈的功能
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode node = root;
        while(!stack.isEmpty() || node != null){
            while(node != null){
                // 首先拿到的是 根节点
                // 然后依次往下循环，获取到左节点，一直到最后一个左节点，这时栈里的节点都是左节点
                System.out.println(node.val);
                stack.push(node);
                node = node.left;
           }
           // 弹出栈里的左节点，然后依次获取右节点
           node = stack.pop();
           node = node.right;
        }
    }

上面一种的变种：

void preorder(TreeNode root){
    Deque<TreeNode> stack = new LinkedList<>();
    while(root != null || !stack.isEmpty()){
        if(root != null){
            // 在这里获取到的 root 就是前序遍历需要的节点顺序
            System.out.println(root.val);
            stack.push(root);
            root = root.left;
        }else{
            TreeNode node = stack.pop();
            root = node.right;
        }
    }     
}

二叉树的中序遍历：

中序遍历：左节点 -> 根节点 -> 右节点

void inorder(TreeNode root){
    Deque<TreeNode> stack = new LinkedList<>();
     while(!stack.isEmpty() || root != null){
        if(root != null){
            stack.push(root);
            root = root.left;
        }else{
            // 这里获取到的节点就是中序遍历的节点
            TreeNode node = stack.pop();
            System.out.println(node.val);
            root = node.right;
        }
    }   
}

上面中序遍历的变种：
下面的中序遍历，也是先沿着一条线访问并入栈左节点，当轮询到的左节点为空时，表明当前的一条线走完，这条线上除了最后一个的左节点，同时也是其它节点父节点，所以出栈后就有可能是根节点。根据中序遍历的特点，出栈的节点就可以当做是遍历的需要点节点。走完左节点这一条线后，然后根据栈中保存的左节点，查找它的右节点，然后把这个右节点当做根节点再重复上面的步骤。

void inorder(TreeNode root){
    Deque<TreeNode> stack = new LinkedList<>();
    while(root != null || !stack.isEmpty()){
        while(root != null){
            stack.push(root);
            root = root.left;
        }
        TreeNode node = stack.pop();
        // 这里获取到的节点就是中序遍历的节点
        System.out.println(node.val);
        root = node.right;
    }  
}

二叉树的后序遍历：

二叉树的后序循环遍历，个人认为比较难。不过可以在上面的前序遍历中的第一种方式的基础上做一下改变，就可以的到后序遍历方式。

void postorder(TreeNode root){
    Deque<Integer> res = new LinkedList<>();
    Deque<TreeNode> stack = new LinkedList<>();
    stack.push(root);
    while(!stack.isEmpty()){
        // 将这里获取的节点是压入栈，当循环结束后，出栈的顺序就是后序遍历的
        // 除根几点外，在入栈时，是先左节点入栈，后右节点入栈。
        // 那么出栈时就是 先右节点出栈，后左节点出栈。加上最先出栈的根节点。
        // 正常的出栈顺序就是 根节点 -> 右节点 -> 左节点
        // 所以就需要存入另一个栈时，在出栈是就是 左节点 -> 右节点 -> 根节点，即后序遍历
        TreeNode node = stack.pop();
        if(node == null){
            continue;
        }            
        res.push(node.val);
        // 先左节点入栈，后右节点入栈
        if(node.left != null){
            stack.push(node.left);
        }
        if(node.right != null){
            stack.push(node.right);
        }
    }
}

另一种后序遍历：

    void postorder(TreeNode root){
        if(root == null){
            return;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode prev = null;
        while(root != null || !stack.isEmpty()){
            // 沿一条线，将其中的左节点压入栈中
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            // 取出栈中一个节点，查看其是否存在右节点，或者其右节点是否是上一个节点
            root = stack.pop();
            if(root.right == null || root.right == prev){
                ans.add(root.val);
                prev = root;
                root = null;
            }else{
                stack.push(root);
                root = root.right;
            }
        }
    }

Review/Share：

Android Studio 升级后的修改