二叉树遍历

144. 二叉树的前序遍历

题目

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例 1：

输入：root = [1,null,2,3]
输出：[1,2,3]

答案

class Solution {
    List res = new ArrayList();
    public List preorderTraversal(TreeNode root) {
        if(root==null){
            return res;
        }
        deal(root);
        return res;
    }
    void deal(TreeNode root){
        if(root==null){
            return;
        }
        res.add(root.val);
        deal(root.left);
        deal(root.right);
    }
}
class Solution {
    List res = new ArrayList();
    public List preorderTraversal(TreeNode root) {
        if(root==null){
            return res;
        }
        Stack stack = new Stack();
        stack.push(root);
        while(!stack.isEmpty()){ // 根 左 右
            TreeNode curr = stack.pop();
            res.add(curr.val);
            if(curr.right!=null){
                stack.push(curr.right);
            }
            if(curr.left!=null){
                stack.push(curr.left);
            }
        }
        return res;
    }
}

145. 二叉树的后序遍历

题目

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

示例 1：

输入：root = [1,null,2,3]
输出：[3,2,1]

答案

class Solution {
    List res = new ArrayList();
    public List postorderTraversal(TreeNode root) {
        if(root==null){
            return res;
        }
        deal(root);
        return res;
    }
    void deal(TreeNode root){
        if(root==null){
            return;
        }
        deal(root.left);
        deal(root.right);
        res.add(root.val);
    }
}
class Solution {
    List res = new ArrayList();
    public List postorderTraversal(TreeNode root) {
        if(root==null){
            return res;
        }
        Stack stack = new Stack();
        stack.push(root);
        while(!stack.isEmpty()){//根 右 左 -》 左 右 根
            TreeNode curr = stack.pop();
            res.add(curr.val);
            if(curr.left!=null){
                stack.push(curr.left);
            }
            if(curr.right!=null){
                stack.push(curr.right);
            }
        }
        Collections.reverse(res);
        return res;
    }
}

94. 二叉树的中序遍历

题目

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

答案

class Solution {
    List res = new ArrayList();
    public List inorderTraversal(TreeNode root) {
        if(root==null){
            return res;
        }
        deal(root);
        return res;
    }
    void deal(TreeNode root){
        if(root==null){
            return;
        }
        deal(root.left);
        res.add(root.val);
        deal(root.right);
    }
}

102. 二叉树的层序遍历

题目

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

答案

class Solution {
    public List levelOrder(TreeNode root) {
        List res = new ArrayList();
        if(root==null){
            return res;
        }
        Queue queue = new LinkedList();
        queue.offer(root);
        while(!queue.isEmpty()){
            List list = new ArrayList();
            int size = queue.size();
            for(int i=0;i
                TreeNode curr = queue.poll();
                list.add(curr.val);
                if(curr.left!=null) queue.offer(curr.left);
                if(curr.right!=null) queue.offer(curr.right);
            }
            res.add(list);
        }
        return res;
    }
}

    public List
        LinkedList
            return res;
        }
        Queue
            List
                TreeNode curr = queue.poll();
                list.add(curr.val);
                if(curr.left!=null) queue.offer(curr.left);
                if(curr.right!=null) queue.offer(curr.right);
            }
            res.addFirst(list);//利用LinkedList addFirst()
        }
        return res;
    }
}

    public List
        List
            return res;
        }
        Queue
            int size = queue.size();
            for(int i=0;i
                TreeNode curr = queue.poll();
                if(i==size-1) res.add(curr.val);
                if(curr.left!=null) queue.offer(curr.left);
                if(curr.right!=null) queue.offer(curr.right);
            }
        }
        return res;
    }
}

    public List
        List
            return res;
        }
        Queue
            double sum = 0;
            int size = queue.size();
            for(int i=0;i
                TreeNode curr = queue.poll();
                sum += curr.val;
                if(curr.left!=null) queue.offer(curr.left);
                if(curr.right!=null) queue.offer(curr.right);
            }
            res.add(sum/size);
        }
        return res;
    }
}

    public List
        List
            return res;
        }
        Queue
            List
                Node curr = queue.poll();
                list.add(curr.val);
                for(Node child : curr.children){
                    queue.offer(child);
                }
            }
            res.add(list);
        }
        return res;
    }
}

    public List
        List
            return res;
        }
        Queue
            int max = Integer.MIN_VALUE;
            int size = queue.size();
            for(int i=0;i
                TreeNode curr = queue.poll();
                max = Math.max(max,curr.val);
                if(curr.left!=null) queue.offer(curr.left);
                if(curr.right!=null) queue.offer(curr.right);
            }
            res.add(max);
        }
        return res;
    }
}

    public Node connect(Node root) {
        if(root==null){
            return root;
        }
        Queue
            int size = queue.size();
            Node pre = queue.poll();
            if(pre.left!=null) queue.offer(pre.left);
            if(pre.right!=null) queue.offer(pre.right);
            for(int i=1;i
                Node curr = queue.poll();
                pre.next = curr;
                pre = curr;
                if(curr.left!=null) queue.offer(curr.left);
                if(curr.right!=null) queue.offer(curr.right);
            }
        }
        return root;
    }
}

    public Node connect(Node root) {
        if(root==null){
            return root;
        }
        Queue
            int size = queue.size();
            Node pre = queue.poll();
            if(pre.left!=null) queue.offer(pre.left);
            if(pre.right!=null) queue.offer(pre.right);
            for(int i=1;i
                Node curr = queue.poll();
                pre.next = curr;
                pre = curr;
                if(curr.left!=null) queue.offer(curr.left);
                if(curr.right!=null) queue.offer(curr.right);
            }
        }
        return root;
    }
}

    public int maxDepth(TreeNode root) {
        int res = 0;
        if(root==null){
            return res;
        }
        Queue
            int size = queue.size();
            for(int i=0;i
                TreeNode curr = queue.poll();
                if(curr.left!=null) queue.offer(curr.left);
                if(curr.right!=null) queue.offer(curr.right);
            }
            res++;
        }
        return res;
    }
}

    public int minDepth(TreeNode root) {
        int res = 0;
        if(root==null){
            return res;
        }
        Queue
            int size = queue.size();
            res++;
            for(int i=0;i
                TreeNode curr = queue.poll();
                if(curr.left==null && curr.right==null){
                    return res;
                }
                if(curr.left!=null) queue.offer(curr.left);
                if(curr.right!=null) queue.offer(curr.right);
            }
        }
        return res;
    }
}