牛客面试必刷TOP101

03二叉树

四种主要的遍历思想为：

前序遍历：根结点 —> 左子树 —> 右子树

中序遍历：左子树—> 根结点 —> 右子树

后序遍历：左子树 —> 右子树 —> 根结点

层次遍历：只需按层次遍历即可

BM23 二叉树的前序遍历

public class Solution {
    ArrayList<Integer> list = new ArrayList<>();
    public int[] preorderTraversal (TreeNode root) {
        if(root == null)return new int[0];
        recur(root);
        
        //循环遍历到数组
        int[] res = new int[list.size()];
        for(int i = 0; i < list.size(); i++){
            res[i] = list.get(i);
        }
        return res;
               
    }
    //递归
    public void recur(TreeNode root){
        if(root == null)return;
        list.add(root.val);
        recur(root.left);
        recur(root.right);
    }
}

BM24 二叉树的中序遍历

public class Solution {
    ArrayList<Integer> list = new ArrayList<>();   
    public int[] inorderTraversal (TreeNode root) {
        if(root == null)return new int[0];
        recur(root);
        
        //循环遍历到数组
        int[] arr = new int[list.size()];
        for(int i = 0 ; i < list.size(); i++){
            arr[i] = list.get(i);
        }
        return arr;    
    }
    //递归
    public void recur (TreeNode root) {
        if(root == null)return;   
        recur(root.left);
        list.add(root.val);
        recur(root.right);  
    }
}

BM25 二叉树的后序遍历

public class Solution {
    ArrayList<Integer> list = new ArrayList<>();   
    public int[] inorderTraversal (TreeNode root) {
        if(root == null)return new int[0];
        recur(root);
        
        //循环遍历到数组
        int[] arr = new int[list.size()];
        for(int i = 0 ; i < list.size(); i++){
            arr[i] = list.get(i);
        }
        return arr;    
    }
    //递归
    public void recur (TreeNode root) {
        if(root == null)return;
        recur(root.left);
        recur(root.right);
        list.add(root.val);
    }
}

BM26 求二叉树的层序遍历

public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        if(root == null)return null;
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        stack.addLast(root);
        while(!stack.isEmpty()){
            ArrayList<Integer> list = new ArrayList<>(); 
             for(int i = stack.size() ; i > 0 ; i--){
                 TreeNode temp = stack.pollFirst();
                 list.add(temp.val);
                 if(temp.left != null)stack.addLast(temp.left);
                 if(temp.right != null)stack.addLast(temp.right);
             }
            res.add(list);
        }
        return res;
    }
}

BM27 按之字形顺序打印二叉树

public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        
        if(pRoot == null)return new ArrayList<ArrayList<Integer>>();
     
        stack.add(pRoot);
        ArrayList<Integer> temp;
//这里比较坑，不能直接奇数偶数行合成一起，要分开
//直接这样理解，不管奇数行偶数行，都需要把队列中元素按照从左往右的顺序拍好。
//首先是偶数行，偶数行要从左往右打印，所以我们移除首元素，所以往队列末添加，就是从左往右添加到末尾
        while(!stack.isEmpty()){
            temp = new ArrayList<>();
            for(int i = stack.size() ; i > 0 ; i-- ){
                TreeNode node = stack.removeFirst();
                temp.add(node.val);
                if(node.left!=null)stack.addLast(node.left);
                if(node.right!=null)stack.addLast(node.right);
            }
            list.add(temp);
            if(stack.isEmpty())break;
//然后是奇数行，要从右往左打印，所以移除最后，然后往队列首添加，先右后左到队列首部。
            temp = new ArrayList<>();
            for(int i = stack.size() ; i > 0 ; i-- ){
                TreeNode node = stack.removeLast();
                temp.add(node.val);
                if(node.right!=null)stack.addFirst(node.right);
                if(node.left!=null)stack.addFirst(node.left);
            }
            list.add(temp);
        }
        return list;
    }
}

BM28 二叉树的最大深度

public class Solution {
    //直接递归
    public int maxDepth (TreeNode root) {
        if(root == null)return 0;
        return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }
}

BM29 二叉树中和为某一值的路径(一)

给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。

1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点

2.叶子节点是指没有子节点的节点

3.路径只能从父节点到子节点，不能从子节点到父节点

4.总节点数目为n

注意，这个题要求是从父节点一直到根节点，不是中间节点，所以最后要判断这个节点没有左右子节点。

public class Solution {
    public boolean hasPathSum (TreeNode root, int sum) {
        if(root == null)return false;
        sum -= root.val;
        if(root.left == null && root.right == null && sum == 0)return true;
        return hasPathSum(root.left , sum ) || hasPathSum(root.right , sum );
    }
}

BM30 二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示

数据范围：输入二叉树的节点数 0≤n≤1000，二叉树中每个节点的值 0≤val≤1000
要求：空间复杂度O(1)（即在原树上操作），时间复杂度 O(n)

注意:

1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继

2.返回链表中的第一个节点的指针

3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构

4.你不用输出双向链表，程序会根据你的返回值自动打印输出

示例1

输入：
{10,6,14,4,8,12,16}
返回值：From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4;
说明：
输入题面图中二叉树，输出的时候将双向链表的头节点返回即可。     

示例2

输入：

输入：
{5,4,#,3,#,2,#,1}
返回值：From left to right are:1,2,3,4,5;From right to left are:5,4,3,2,1;
说明：
                    5
                  /
                4
              /
            3
          /
        2
      /
    1
树的形状如上图