二叉树小结

二叉树的定义：

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;
    }
}

二叉树的遍历：

前序遍历：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> lst = new ArrayList<>();
        preorder(root, lst);
        return lst;
    }

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

中序遍历：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> lst = new ArrayList<>();
        inorder(root, lst);
        return lst;
    }

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

后序遍历：

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> lst = new ArrayList<>();
        postorder(root, lst);
        return lst;
    }

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

层序遍历：

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        bfs(root, ans);
        return ans;
    }
//队列
    public void bfs(TreeNode root, List<List<Integer>> ans){
        if(root == null){
            return;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            int len = q.size();
            List<Integer> lst = new ArrayList<>();

            while(len > 0){
                TreeNode node = q.remove();
                lst.add(node.val);

                if(node.left != null) q.add(node.left);
                if(node.right != null) q.add(node.right);
                len--;
            }
            ans.add(lst);
        }
    }
}

示例：

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