华为冲刺--二叉树部分

1递归遍历二叉树

1. 1 前序遍历：递归法

//前序遍历
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {

        List<Integer> list=new ArrayList();
        //调用递归函数
        preorder(root , list);
        return list;
    }

    public static void preorder(TreeNode root,List<Integer> list){
        
        //1)截止条件
        if(root==null) return;

		//2)操作
        list.add(root.val);
        //3）递归函数
        preorder(root.left,list);
        preorder(root.right,list);
    }
}

1. 2 前序遍历：迭代法（深度优先算法）

1. 思路
   1）前序遍历的顺序中左右，那么只需要把入栈的顺序改为中-右-左即可。这样出栈顺序就是中-左-右了
   2）代码书写过程类似层序遍历，
   （1）：定义集合和栈
   （2）：把首节点放进去
   （3）：开始进行遍历操作，一层while循环，然后就是先出栈后压栈（顺序为中右边左边）
2. 代码

//前序遍历
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        //方法二：迭代解法

        //1）定义集合和栈
        List<Integer> list=new ArrayList<>();
        ArrayDeque<TreeNode> deque=new ArrayDeque<>();

        //2)特殊情况
        if(root==null) return list;
        deque.push(root);

        //3)进行循环
        while(deque.size()>0){
            //先删除父节点，然后判断压入子节点(从右到左)
            TreeNode fa=deque.pop();
            list.add(fa.val);
            if(fa.right!=null) deque.push(fa.right) ;
            if(fa.left!=null) deque.push(fa.left) ;
        }

        //4)返回结果
        return list;
    }
}

//后续遍历
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        //迭代方法
        //需要的结果是左右中，可以先做出来中右左-反转得到左右中
        //为了得到中右左，故压栈的顺序为中左右

        //1）集合和栈的定义
        List<Integer> list=new ArrayList<>();
        ArrayDeque<TreeNode> deque=new ArrayDeque<>();

        //2)特殊情况
        if(root==null) return list;
        deque.push(root);

        //3)开始循环遍历
        while(deque.size()>0){
            TreeNode temp=deque.pop();   
            list.add(temp.val);   //中间
            if(temp.left!=null) deque.push(temp.left);
            if(temp.right!=null) deque.push(temp.right);
        }
        //4）进行反转
        Collections.reverse(list);
        return list;
    }
}

1. 3 层序遍历：迭代法

1. 思路步骤
   1） 定义二维数组集合与队列
   2）特殊情况先考虑,并把根节点放进去
   3）根节点不为空，那么就一层一层放东西（两层while循环）
   （1）第一层while循环，得到目前队列的大小，判断是否还有下一层，然后把上一层的数据装载入集合中
   （2） 第二层while循环，（先存子节点，和父节点值，再删父节点）循环遍历队列中的元素，看子节点是否存在，存在就进行输入队列，然后把父节点值存入，再删除父节点。
   （3）在第一层里，第二层外，把每一层的数据存起来。
   4）输出二维集合数据
2. 代码展示

    public List<List<Integer>> levelOrder(TreeNode root) {
        //1）新建集合和队列
        List<List<Integer>> data=new ArrayList<>();
        ArrayDeque<TreeNode> deque=new ArrayDeque<>();

        //特殊情况
        if(root==null) return data;
        deque.offer(root);

        //3)两层while循环
        int size;
        while(deque.size()!=0){
            //(1)新建一维集合装数据，计算size的大小，方便二层循环
            List<Integer> list=new ArrayList<>();
            size=deque.size();
            while(size-->0){
                //(2)先把数据装进行，然后看子节点是否需要装入队列中
                if(deque.peek().left!=null) deque.offer(deque.peek().left);
                if(deque.peek().right!=null) deque.offer(deque.peek().right);
                list.add(deque.poll().val); //查找的同时进行删除
            }
            data.add(list);
        }
        return data;

    }

3. 总结
   1）层序遍历是一个经典的bfs算法（广度搜索算法）。对一个地方都会进行遍历一遍，能够解决很多类似问题
   2）能够解决一些类型问题