LeetCode刷题—二叉树的遍历

发表于 2020-12-20 分类于 LeetCode刷题

此篇用于梳理二叉树的遍历方式：深度优先遍历（前、中、后序遍历）和广度优先遍历，不仅能快速领会思想和总结规律，还可以顺便刷下这些题：

94，二叉树的中序遍历，medium 102，二叉树的层序遍历，easy 230，二叉搜索树中第k小的元素，medium 501，二叉搜索树中的众数，easy 530，二叉树搜索树的最小绝对差，easy

530，二叉树搜索树的最小绝对差，easy

一、二叉树的遍历有四种方式：

1. 前序遍历：根-左-右

2. 中序遍历：左-根-右

3. 后序遍历：左-右-根

4. 层次遍历：BFS + 分层存储

例如：

- 前序遍历顺序：[1 2 4 5 3 6] （中-左-右） - 中序遍历顺序：[4 2 5 1 3 6] （左-中-右） - 后序遍历顺序：[4 5 2 6 3 1] （右-左-中） - 层次遍历顺序：[1 2 3 4 5 6]

层次遍历使用 BFS 实现，利用的就是 BFS 一层一层遍历的特性；而前序、中序、后序遍历利用了 DFS 实现。

前序、中序、后序遍只是在对节点访问的顺序有一点不同，其它都相同。

注意：对于二叉搜索树，常进行中序遍历，其结果由小到大的顺序有时对解题很有帮助。 ## 二、二叉树遍历的模板 ##### 1. 前序遍历：根-左-右

//前序遍历
void preorderTraversal(TreeNode root){
    visit(root);
    preorderTraversal(root.left);
    preorderTraversal(root.right);
}

##### 2. 中序遍历：左-根-右

//中序遍历
void inorderTraversal(TreeNode root){
    preorderTraversal(root.left);
    visit(root);
    preorderTraversal(root.right);
}

3. 后序遍历：左-右-根

//后序遍历
void postorderTraversal(TreeNode root){
    preorderTraversal(root.left);
    preorderTraversal(root.right);
    visit(root);
}

4. 层次遍历

使用【队列】来由上至下由左至右遍历，队列由 LinkedList 实现。

三、实现（递归与迭代两种方式）

1. 前序遍历：根-左-右

LeetCode的144题：二叉树的前序遍历

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

示例 1：

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

方法一：递归。

 class Solution { 
public List<Integer> preorderTraversal(TreeNode root) {
       List<Integer> res  = new ArrayList<>();
       dfs(root, res);
       return res;
   }
   public List<Integer> dfs(TreeNode root, List<Integer> res){
       if(root == null) return null;

       res.add(root.val);
       dfs(root.left, res);
       dfs(root.right, res);
       return res;
   }
  }

方法二：迭代。借助栈。

思路：首先应该创建一个Stack用来存放节点，首先我们想要打印根节点的数据，此时Stack里面的内容为空，所以我们优先将头结点加入Stack，然后打印。
之后应该先打印左子树，然后右子树。所以先加入Stack的就是右子树，然后左子树。

代码：

class Solution {

 public List<Integer> preorderTraversal(TreeNode root) {
     if(root == null) return new ArrayList<>();
     List<Integer> res = new ArrayList<>();
     Stack<TreeNode> stack = new Stack<>();

     stack.push(root);
     while(!stack.isEmpty()){
         TreeNode node = stack.pop();
         res.add(node.val);
          //栈先进后出，为保证左边的子节点先弹出，把右子节点压入栈
         if(node.right != null) stack.push(node.right);
         if(node.left != null) stack.push(node.left);
     }
     return res;
 }

2. 中序遍历：左-根-右

LeetCode的94题：二叉树的中序遍历

方法一：递归。

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
       List<Integer> res = new ArrayList<>();
       dfs(root, res);
       return res;
   }
   public void dfs(TreeNode root, List<Integer> res){
       //左中右
       if(root == null) return ;
       dfs(root.left, res);
       res.add(root.val);
       dfs(root.right, res);
   }
   }

方法二：迭代。

思路：从根节点向左找到最后一个左子节点，并压入栈。弹出栈顶节点，并加入结果集。再找此节点的右子节点，如果为空将弹出根节点。

代码：

class Solution {
   public List<Integer> inorderTraversal(TreeNode root) {
       if(root == null) return new ArrayList<>();

       List<Integer> res = new ArrayList<>();
       Stack<TreeNode> stack = new Stack<>();
    
       while(root != null || !stack.isEmpty()){
           //向左找左子节点
           while(root != null){
               //将左子节点入栈
               stack.push(root);
               root = root.left;
           }
           //找到左子树最后一个左子节点弹出并添加至结果集
           root = stack.pop();
           res.add(root.val);
           //找此节点的右子节点进入上面循环
           root = root.right;  
       }
       return res;
   }
   ｝

##### 3. 后序遍历：左-右-根 ###### LeetCode的145题：二叉树的后序遍历

方法一：递归。

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
       List<Integer> res = new ArrayList<>();
       dfs(root, res);
       return res;
   }
   public void dfs(TreeNode root, List<Integer> res){
       //左右中
       if(root == null) return ;
       dfs(root.left, res);
       dfs(root.right, res);
       res.add(root.val);
   }
   }

方法二：迭代。前序遍历的结果倒序添加。

class Solution {
   public List<Integer> postorderTraversal(TreeNode root) {
       if(root == null) return new ArrayList<>();
       List<Integer> res = new ArrayList<>();
       Stack<TreeNode> stack = new Stack<>();
       if(root != null) stack.push(root);
       while(!stack.isEmpty()){
           TreeNode node = stack.pop();
           if(node.left != null) stack.push(node.left);
           if(node.right != null) stack.push(node.right);
           
           res.add(0, node.val);
       }
       return res;
   }
   }

##### 4. 层次遍历：BFS遍历 + 分层

//BFS遍历实现
public void bfs(TreeNode root){
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while(!queue.isEmpty()){
        int size = queue.size();
        for(int i = 0; i < size; i++){
            TreeNode node = queue.poll();
        	if(node.left != null){
            	queue.add(node.left);
        	}
        	if(node.right != null){
            	queue.add(node.right);
        	}
        }
    }
}

LeetCode的102题：二叉树的层次遍历

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

示例：二叉树：[3,9,20,null,null,15,7],

返回其层次遍历结果：

[ [3], [9,20], [15,7]]

思路：由上面BFS遍历过程，稍加修改，即将每层的节点序列存储到集合temp中，再将每一层添加至List<List<Integer>> res即可
代码：

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if(root != null)
            queue.add(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> temp = new ArrayList<>();
            for(int i = 0; i < size; i++){
                TreeNode node = queue.poll();
                temp.add(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            //将每层添加至结果集
            res.add(temp);
        }
        return res;
    }
}

四、二叉搜索树的中序遍历

由于BST树左小右大、中序遍历的结果由小到大，常利用这一结论来解题。如： ###### LeetCode的230题：二叉搜索树中第k小的元素给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

说明：你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

示例 1:

输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 1

思路：直接应用上面中序遍历的结果，返回 list 的第 k - 1 个元素即可。

递归

class Solution {
  public int kthSmallest(TreeNode root, int k) {
      List<TreeNode> res = new ArrayList<>();
      helper(root, res);       
      return res.get(k - 1).val;
  }
  //中序遍历结果
  public void helper(TreeNode root, List<TreeNode> list){
      if(root == null) return;
      helper(root.left, list);
      list.add(root);
      helper(root.right, list);
  }
}

迭代

class Solution {
  public int kthSmallest(TreeNode root, int k) {
      if(root == null) return -1;
      Stack<TreeNode> stack = new Stack<>();
   
      while(root != null || !stack.isEmpty()){
          //向左找左子节点
          while(root != null){
              //将左子节点入栈
              stack.push(root);
              root = root.left;
          }
          //找到左子树最后一个左子节点弹出并添加至结果集
          root = stack.pop();
          //找到第k小的节点
          k--;
          if(k == 0) return root.val;
          //找此节点的右子节点进入上面循环
          root = root.right;  
      }
      return -1;
  }
}

###### LeetCode的501题：二叉搜索树中的众数给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。

假定 BST 有如下定义：

结点左子树中所含结点的值小于等于当前结点的值结点右子树中所含结点的值大于等于当前结点的值左子树和右子树都是二叉搜索树

例如：给定 BST [1,null,2,2],

返回[2].

提示：如果众数超过1个，不需考虑输出顺序 - 方法：改造中序遍历。

思路：

加入全局变量当前节点值curVal，当前节点出现次数count，最大出现的次数maxCount

如果当前节点值 root.val == curVal，count++
如果不等于curVal，说明遇到下一个新的值，更新curVal = root.val ，且 count = 1

比较 count 与 maxCount

如果相等，添加到结果集中

如果count > maxCount，清空结果集，并把节点值 root.val 加入结果集，更新maxCount = count

class Solution {
int curVal;//当前节点的值
  	int count;//cur节点的次数
 	int maxCount;//当前的最大次数
  	List<Integer> res = new ArrayList<>();
  	public int[] findMode(TreeNode root) {
      	inorder(root);
      	int[] ans = new int[res.size()];
      	for(int i = 0; i < res.size(); i++){
          	ans[i] = res.get(i);
      	}
      	return ans; 
  	}
  	public void inorder(TreeNode root){
      	if(root == null) return;
      	inorder(root.left);
  //如果当前节点值 node.val = cur，count + 1
      	int rootVal = root.val;
      	if(rootVal == curVal){
          	count++;
      	}
  // 如果不等于cur，说明遇到下一个新的值，更新cur，且count = 1
      	else{
          	curVal = rootVal;
          	count = 1;
      	}
      //比较count 与 maxCount
  // 如果相等，添加到结果集中
      	if(count == maxCount){
         	res.add(rootVal);
      	}
  // 如果count > maxCount，清空结果集，并把节点值 node.val 加入结果集，更新maxCount = count
      	else if(count > maxCount){
          	res.clear();
          	res.add(rootVal);
         	maxCount = count;
     	 }
      	inorder(root.right);
  	}
}

###### LeetCode的530题：二叉树搜索树的最小绝对差给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。

示例：输入：

输出： 1

解释：最小绝对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。 - 方法：改造中序遍历。因为二叉搜索树的中序遍历结果是升序的，我们只需要在中序遍历的时候和前一个节点比较，保存最小的差值即可。建立前一个节点作为全局变量。

递归：

class Solution {
  TreeNode pre;//前一个节点
  int min = Integer.MAX_VALUE;
  public int getMinimumDifference(TreeNode root) {
      inorder(root);
      return min;
  }
  public void inorder(TreeNode root){
      if(root == null) return;
      inorder(root.left);
      if(pre != null)
          min = Math.min(min, root.val - pre.val);
      pre = root;//更新pre到下个节点
      inorder(root.right);
  }  
}

迭代

public int getMinimumDifference(TreeNode root) {
      int min = Integer.MAX_VALUE;
      Stack<TreeNode> stack = new Stack<>();
      TreeNode cur = root, prev = null;
      while (cur != null || !stack.empty()) {
          if (cur != null) {
              stack.push(cur);
              cur = cur.left;
          } else {
              cur = stack.pop();
              //在这里进行改造
              if (prev != null)
                  min = Math.min(min, cur.val - prev.val);
              prev = cur;
              
              cur = cur.right;
          }
      }
      return min;
  }

------ 本文结束感谢您的阅读 ------