二叉树

二叉树的遍历

深度优先遍历

前序遍历

    void preorderTraversal(TreeNode root, List<Integer> list){
        if ( root == null )
            return ;
        list.add(root.val);
        preorderTraversal(root.left, list);
        preorderTraversal(root.right, list);
    }

    List<Integer> preorderTraversal(TreeNode root){
        List<Integer> result = new ArrayList<>();
        if (root == null)
            return result;
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        stack.addLast(root);
        while ( !stack.isEmpty() ){
             TreeNode node = stack.pollLast();
             result.add(node.val);
             if (node.right != null){
                 stack.addLast(node.right);
             }
             if (node.left != null){
                 stack.addLast(node.left);
             }
        }
        return result;
    }

中序遍历

    void inorderTraversal(TreeNode root, List<Integer> list){
        if ( root == null )
            return;
        inorderTraversal(root.left, list);
        list.add(root.val);
        inorderTraversal(root.right, list);
    }

    List<Integer> inorderTraversal(TreeNode root){
        List<Integer> result = new ArrayList<>();
        if (root == null)
            return res;
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root; //定义一个指针用来访问节点
        //这里不是立刻添加root结点到栈中
        //因为没有立刻添加，所以栈一开始可能是空的，得加个条件进循环
        while ( cur!=null || !stack.isEmpty()){ //当指针为空或者栈为空时结束循环
            if ( cur!=null ){ //没有访问到叶子结点
                stack.addLast(cur);
                cur = cur.left;
            }else{
                cur = stack.pollLast();//当cur为空时，左边访问到底了，弹出元素即为左叶子结点
                result.add(cur.val);
                cur = cur.right;//访问右子树
            }
        }
        return result;
    }

后序遍历

    void postorderTraversal(TreeNode root, List<Integer> list){
        if ( root == null )
            return;
        postorderTraversal(root.left, list);
        postorderTraversal(root.right, list);
        list.add(root.val);
    }

    List<Integer> postorderTraversal(TreeNode root){
        List<Integer> result = new ArrayList<>();
        if (root == null)
            return result;
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();
        stack.addLast(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pollLast();
            result.add(node.val);
            if (node.left!=null)
                stack.addLast(node.left);
            if (node.right!=null)
                stack.addLast(node.right);
        }
        Collections.reverse(result);
        return result;
    }

广度优先遍历

层次遍历

• 递归

    public List<List<Integer>> resList = new ArrayList<>(); 
    void levelOrderTraversal(TreeNode root, Integer deep){
        if (root == null)
            return;
        //如果节点不为空，说明存在下一层，deep++
        //此时，下一层为deep，当前层为deep-1
        deep++; 
        if (resList.size() < deep){
            //判断该层是否创建过了
            List<Integer> item = new ArrayList<>();
            resList.add(item);
        }
        resList.get(deep-1).add(root.val);
        levelOrderTraversal(root.left,deep);
        levelOrderTraversal(root.right,deep);
    }
  

• 迭代

    public List<List<Integer>> resList = new ArrayList<>();
    void levelOrderTraversal(TreeNode root){
        if (root == null) 
            return;
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.addLast(root);
        while (!queue.isEmpty()){
            List<Integer> item = new ArrayList<>();
            int len = queue.size();
            while ( len > 0 ){ //这里不能直接用queue.size()，因为queue长度在不断变化
                TreeNode node = queue.pollFirst();
                item.add(node.val);
                if (node.left!=null)
                    queue.addLast(node.left);
                if (node.right!=null)
                    queue.addLast(node.right);
                len--;
            }
            resList.add(item);
        }
    }