二叉树专题01------树的基础知识，遍历方式、前序遍历、中序遍历和后序遍历、递归、迭代、DFS、BFS、层序遍历

二叉树基础知识可以看一下这里，就不列举了，有前人栽的树，我们就乘凉，感谢前辈们！！！

第一题：二叉树的递归遍历

力扣144题
代码如下：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        //返回的结果
        List<Integer> res = new ArrayList<>();
        preOrder(root, res);
        return res;
    }
    //前序遍历就是先遍历中间节点，再遍历左节点，最后是右节点
    void preOrder(TreeNode root, List<Integer> res) {
        if(root == null) {
            return;
        }
        res.add(root.val);//中间
        preOrder(root.left, res);//左边
        preOrder(root.right, res);//右边
    }
}

力扣145题
代码如下：

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        //返回结果
        List<Integer> res = new ArrayList<>();
        postOrder(root, res);
        return res;
    }
    //后序遍历就是先遍历左节点，再遍历右节点，最后是中间节点
    void postOrder(TreeNode root, List<Integer> res) {
        if(root == null) {
            return;
        }
        postOrder(root.left, res);//左点
        postOrder(root.right, res);//右点
        res.add(root.val);//中间
    }
}

力扣94题
代码如下：
//递归法（简单）

class Solution {
	//递归法（简单）
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inOrder(root, res);
        return res;
    }
    //中序遍历就是先遍历左节点，再遍历中节点，最后是右节点
    void inOrder(TreeNode root, List<Integer> res) {
        if(root == null) {
            return;
        }
        inOrder(root.left, res);//左点
        res.add(root.val);//中点
        inOrder(root.right, res);//右点
    }
}

迭代法（常用）===》思路就是，从root开始，把左树的左节点全部压入栈中，直到p为空，那就把栈顶的值（也就是某一个不为空的根节点）赋给p，把此时p的值添加到res中，之后把p指向p的右节点，重复这个过程，直到p为空并且栈也为空。

class Solution {
    //迭代法（常用）
    public List<Integer> inorderTraversal(TreeNode root) {
        //存放结果
        List<Integer> res = new ArrayList<>();
        //开个栈
        Stack<TreeNode> stack = new Stack<>();
        TreeNode p = root;
        while(p != null || !stack.isEmpty()) {
            //从根节点开始，把左树节点全部压入栈中
            while(p != null) {
                stack.push(p);
                p = p.left;
            }
            p = stack.pop();
            res.add(p.val);
            p = p.right;
        }
        return res;
    }

第二题：力扣98题

解题思路：

先搞清楚什么是有效的 二叉搜索树，定义如下：

1. 节点的左子树只包含 小于 当前节点的数。
2. 节点的右子树只包含 大于 当前节点的数。
3. 所有左子树和右子树自身必须也是二叉搜索树。

我们判断根节点的值与左右节点的值大小关系来递归解题即可。

代码如下：

class Solution {
    public boolean isValidBST(TreeNode root) {
        //传参
        return def(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    //递归
    public boolean def(TreeNode root, long lower, long upper) {
        if(root == null) {
            return true;
        }
        if(root.val <= lower || root.val >= upper) {
            return false;
        }
        return def(root.left, lower, root.val) && def(root.right, root.val, upper);
    }
}

第三题：力扣101题

代码如下：

				方法一：递归

class Solution {
    //方法一：递归
    public boolean isSymmetric(TreeNode root) {
        if(root == null) {
            return true;
        }
        return def(root.left, root.right);
    }
    boolean def(TreeNode p, TreeNode q) {
        if(p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        return p.val == q.val && def(p.left, q.right) && def(p.right, q.left);
    }
}

方法二：迭代

public boolean isSymmetric(TreeNode root) {
        if(root == null) {
            return true;
        }
        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();
        TreeNode l = root.left;
        TreeNode r = root.right;
        //模仿中序遍历树来写，左右一起遍历，对比
        while(l != null || r != null || !s1.isEmpty() || !s2.isEmpty()) {
            //把左树的左节点，右树的右节点全压入栈
            while(l != null && r != null) {
                s1.push(l);
                l = l.left;
                s2.push(r);
                r = r.right;
            }
            //只要有一个不为null，返回false
            if(l != null || r != null) {
                return false;
            }
            //弹出顶端
            l = s1.pop();
            r = s2.pop();
            //比较值
            if(l.val != r.val) {
                return false;
            }
            //移动，左树往右移动，右树往左移动
            l = l.right;
            r = r.left;
        }
        return true;
    }

第四题：力扣102题

解题思路：

借助队列，先进先出，从根节点开始，算作第一层。在没操作下一层之前，把该层弹出去并返回值，扩充下一层的节点个数，之后再操作下一层！依次往下，直到队列为空，返回各层值的List集合，最后添加至res集合当中吗，返回。（代码有详解）

代码如下：

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        //存放结果用于返回
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) {
            return res;
        }
        //借助队列实现
        Queue<TreeNode> que = new LinkedList<>();
        //将根节点加入队列
        que.offer(root);
        //只要队列不为空就一直进行
        while(!que.isEmpty()) {
            //用于存放每一层的节点值
            List<Integer> levelList = new ArrayList<>();
            //因为每一层的节点数不一样，所以需要用每层的节点数来扩容
            int len = que.size();
            //先弹出上一层节点，再添加下一层节点进去
            for(int i = 0; i < len; i++) {
                //弹出并返回
                TreeNode t = que.poll();
                //将每层的节点值添加到同一个List当中
                levelList.add(t.val);
                //在判断一下左右孩子，有值就加入队列
                if(t.left != null) {
                    que.offer(t.left);
                }
                if(t.right != null) {
                    que.offer(t.right);
                }
            }
            // while(len > 0) {
            //     //弹出并返回
            //     TreeNode t = que.poll();
            //     //将每层的节点值添加到同一个List当中
            //     levelList.add(t.val);
            //     //在判断一下左右孩子，有值就加入队列
            //     if(t.left != null) {
            //         que.offer(t.left);
            //     }
            //     if(t.right != null) {
            //         que.offer(t.right);
            //     }
            //     //将上一层节点数减去
            //     len--;
            // }
            //所有层数都完事之后，将其加到res列表当中
            res.add(levelList);
        }
        return res;
    }
}

第五题：力扣107题

解题思路：

详见代码注释

代码如下：

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        //层序遍历 + 反转List数组
        //层序遍历，参照102
        List<List<Integer>> levelOrder = new ArrayList<>();
        if(root == null) {
            return levelOrder;
        }
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        while(!que.isEmpty()) {
            List<Integer> levelList = new ArrayList<>();
            int len = que.size();
            for(int i = 0; i < len; i++) {
                TreeNode t = que.poll();
                levelList.add(t.val);
                if(t.left != null) {
                    que.offer(t.left);
                }
                if(t.right != null) {
                    que.offer(t.right);
                }
            }
            // while(len > 0) {
            //     TreeNode t = que.poll();
            //     levelList.add(t.val);
            //     if(t.left != null) {
            //         que.offer(t.left);
            //     }
            //     if(t.right != null) {
            //         que.offer(t.right);
            //     }
            //     len--;
            // }
            levelOrder.add(levelList);
        }
        //用一个新的List来装返回答案
        List<List<Integer>> res = new ArrayList<>();
        //头尾复制
        for(int i = levelOrder.size() - 1; i >= 0; i--) {
            res.add(levelOrder.get(i));
        }
        //返回复制完的结果
        return res;
    }
}

第六题：力扣199题

解题思路：

层序遍历的时候，判断是否遍历到单层的最后面的元素，如果是，就放进res数组中，随后返回res就可以

代码如下：

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        //层序遍历的时候，判断是否遍历到单层的最后面的元素，如果是，就放进res数组中，随后返回res就可以
        List<Integer> res = new ArrayList<>();
        if(root == null) {
            return res;
        }
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        while(!que.isEmpty()) {
            int len = que.size();
            for(int i = 0; i < len; i++) {
                TreeNode t = que.poll();
                if(t.left != null) {
                    que.offer(t.left);
                }
                if(t.right != null) {
                    que.offer(t.right);
                }
                if(i == len - 1) {
                    res.add(t.val);
                }
            }
        }
        return res;
    }
}

第七题：力扣637题

解题思路：

本题就是利用层序遍历，对每层进行操作，把一层求个总和之后，再取一个均值。

代码如下：

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        //参照层序遍历===>102
        List<Double> res = new ArrayList<>();
        if(root == null) {
            return res;
        }
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        while(!que.isEmpty()) {
            int levelLen = que.size();
            double levelSum = 0.0;
            for(int i = 0; i < levelLen; i++) {
                TreeNode t = que.poll();
                //每层需要求一下和
                levelSum += t.val;
                if(t.left != null) {
                    que.offer(t.left);
                }
                if(t.right != null) {
                    que.offer(t.right);
                }
            }
            res.add(levelSum / levelLen);
        }
        return res;
    }
}

第八题：力扣429题

解题思路：

还是利用层序遍历的思路完成该题，只不过是N叉树和二叉树对于子节点的表示方式不同罢了！详见代码注释。

代码如下：

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) {
            return res;
        }
        Queue<Node> que = new LinkedList<>();
        que.offer(root);
        while(!que.isEmpty()) {
            List<Integer> levelList = new ArrayList<>();
            int levelLen = que.size();
            for(int i = 0; i < levelLen; i++) {
                Node n = que.poll();
                levelList.add(n.val);
                //这里相当于二叉树的左右节点全加进来，这里换成N叉树的子孩子全加进来！同样有模板
                List<Node> children = n.children;
                for(Node child : children) {
                    if(child != null) {
                        que.offer(child);
                    }
                }
            }
            res.add(levelList);
        }
        return res;
    }
}

第九题：力扣515题

解题思路：

层序遍历，取每一层的最大值

代码如下：

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null) {
            return res;
        }
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        while(!que.isEmpty()) {
            int levelLen = que.size();
            List<Integer> levelVal = new ArrayList<>();
            for(int i = 0; i < levelLen; i++) {
                TreeNode t = que.poll();
                levelVal.add(t.val);
                if(t.left != null) {
                    que.offer(t.left);
                } 
                if(t.right != null) {
                    que.offer(t.right);
                }
            }
            res.add(Collections.max(levelVal));
        }
        return res;
    }
}

第十题：力扣116题

解题思路：

依然是层序遍历的模板，该题需要找到每层的结束加一个标志#，代码中体现在最后一个节点指向null，详见代码注释。

代码如下：

class Solution {
    public Node connect(Node root) {
        if(root == null) {
            return root;
        }
        Queue<Node> que = new LinkedList<>();
        que.offer(root);
        while(!que.isEmpty()) {
            int levelLen = que.size();
            //定义两个指针
            Node nodePre = null;
            Node node = null;
            for(int i = 0; i < levelLen; i++) {
                //取出本层的头一个节点
                if(i == 0)  {
                    nodePre = que.poll();
                    node = nodePre;
                } else {
                    //除本层第一个节点之外的
                    node = que.poll();
                    nodePre.next = node;
                    nodePre = nodePre.next;
                }
                //继续往里添加节点
                if(node.left != null) {
                    que.offer(node.left);
                }
                if(node.right != null) {
                    que.offer(node.right);
                }
            }
            //每层最后一个节点指向null表示该层的结束
            nodePre.next = null;
        }
        return root;
    }
}

第十一题：力扣117题

解题思路和代码：

参见上一题力扣116题

第十二题：力扣104题

解题思路：

还是层序遍历的模板，只不过是仅仅对每层计个数而已嘛，没有什么其他操作！

代码如下：

class Solution {
    public int maxDepth(TreeNode root) {
        int nums = 0;
        if(root == null) {
            return nums;
        }
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        while(!que.isEmpty()) {
            int levelLen = que.size();
            for(int i = 0; i < levelLen; i++) {
                TreeNode t = que.poll();

                if(t.left != null) {
                    que.offer(t.left);
                }
                if(t.right != null) {
                    que.offer(t.right);
                }
            }
            nums++;
        }
        return nums;
    }
}

第十三题：力扣111题

解题思路：

和上一题一样，可用层序遍历的思路来解题，只有当左右子树都为null的时候才是最小深度，只要有一个不是null，那就不是最小深度，完毕！

代码如下：

class Solution {
    public int minDepth(TreeNode root) {
        int nums = 0;
        if(root == null) {
            return nums;
        }
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        while(!que.isEmpty()) {
            int levelLen = que.size();
            nums++;
            for(int i = 0; i < levelLen; i++) {
                TreeNode t = que.poll();
                if(t.left == null && t.right == null) {
                    return nums;
                }
                if(t.left != null) {
                    que.offer(t.left);
                }
                if(t.right != null) {
                    que.offer(t.right);
                }
            }
        }
        return nums;
    }
}

第十四题：力扣226题

解题思路：

可以分别翻转左子树，右子树以及根节点完成树的翻转

代码如下：

方式一：DFS递归

 ***

## //DFS递归（前序遍历和后序遍历都可以，唯独中序遍历不行，因为中序遍历顺序是左中右，导致左子树或者右子树翻转两次）

***
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) {
            return null;
        }
        //前序遍历
        // swapChildren(root);
        // invertTree(root.left);
        // invertTree(root.right);
        
        //后序遍历
        invertTree(root.left);
        invertTree(root.right);
        swapChildren(root);

        return root;
    }
    private void swapChildren(TreeNode root) {
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}

方式二：BFS层序遍历

//BFS层序遍历
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) {
            return root;
        }
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        while(!que.isEmpty()) {
            int levelLen = que.size();
            for(int i = 0; i < levelLen; i++) {
                TreeNode t = que.poll();
                swapChildren(t);
                if(t.left != null) {
                    que.offer(t.left);
                }
                if(t.right != null) {
                    que.offer(t.right);
                }
            }
        }
        return root;
    }
    private void swapChildren(TreeNode root) {
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}