《二叉树》算法面试题：前序、中序、后序、层序遍历

1。二叉树预序遍历

这个问题来自 LeetCode 问题 #144：二叉树预序遍历。

问题描述

给定一个二叉树，返回先序遍历。

问题分析

使用**堆栈**的思路来处理问题。

前序的遍历顺序为：根-左-右。具体算法为：

• 将根节点压入堆栈
• 循环检查堆栈是否为空。如果不存在，则弹出栈顶元素并保存其值
• ，查看对应的子节点是否存在。如果存在，将其压入堆栈
• 以查看其 左子 节点。如果存在，则将其压入堆栈。

动画说明

代码实现

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new LinkedList<>();
        if(root == null){
            return list;
        }
        //第一步是将根节点压入栈中
        stack.push(root);
        //当栈不为空时，出栈的元素插入list尾部。
        while(!stack.isEmpty()){
            root = stack.pop();
            list.add(root.val);
            if(root.right != null) stack.push(root.right);
            if(root.left != null) stack.push(root.left);
        }
        return list;
    }
}
复制代码

2.二叉树的顺序遍历

标题来自LeetCode问题94：二叉树的顺序遍历。

问题描述

给定一个二叉树，按顺序返回其遍历。

问题分析

使用**堆栈**的思路来处理问题。

遍历的顺序为：左-根-右。具体算法如下：

• 从根节点开始，先将根节点压入栈
• ，然后合并所有左子s。单击压入堆栈，将最上面的节点移出堆栈，保存节点值
• ，然后将当前指针移动到右侧子节点。如果有匹配的子节点，则其所有 左子 节点都可以在下一个循环中压入堆栈。

动画说明

代码实现

class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> list = new ArrayList<>();
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root;
            while (cur != null || !stack.isEmpty()) {
                if (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                } else {
                    cur = stack.pop();
                    list.add(cur.val);
                    cur = cur.right;
                }
            }
            return list;
        }
}
复制代码

3.二叉树的后序遍历

标题来自LeetCode问题#145：二叉树的后序遍历。

问题描述

给定一棵二叉树，返回后序遍历。

问题分析

使用**堆栈**的思路来处理问题。

排序后遍历的顺序：左-右-根。具体算法如下：

• 先将根节点压入栈中，然后定义一个辅助节点头
• while循环条件是栈不为空
• 循环中，移除最上面的第一的。栈的节点t
• 如果栈顶节点没有左右子节点，要么左子的节点是头，要么他的右子节点是头的情况。将栈顶节点的值添加到res结果中，将栈顶元素移出栈，然后将头指向栈顶元素
• 否则，如果对应的子节点不是为空，添加到堆栈
• 如果 左子 节点不为空，则添加到堆栈

动画说明

代码实现

public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<Integer>();
    if(root == null)
        return res;
    Stack<TreeNode> stack = new Stack<TreeNode>();
    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.二叉树的层序遍历

标题来自LeetCode第102题：二叉树的层序遍历。

问题描述

二叉树的情况下，返回层次遍历的节点值。 （即从左到右逐层访问所有节点）。

例如：给定一棵二叉树：[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
复制代码

返回一级遍历的结果❙Q❙本题A队列 您必须使用命令。

• 创建等待列表
• 先插入根节点，然后找到根节点的左右两个子节点
• 删除根节点，现在队列的元素都是下一个的节点Layer
• 用法 for循环遍历并将结果存储在一维向量中。平衡二叉树

  标题来自LeetCode问题110：平衡二叉树。

  问题描述

  给定一棵二叉树，判断它是否是高度平衡二叉树。

  查询解析

  接受二叉树每个节点上的后序遍历遍历。

  在移动到一个节点之前，它的左右子树已经被遍历过了，那么遍历每个节点时，只需记录它的深度（节点的深度等于通向叶子节点的路径长度），就可以可以判断遍历过程中各个节点是否平衡。

  代码实现

  class Solution {
      private boolean isBalanced = true;
      public boolean isBalanced(TreeNode root) {
          getDepth(root);
          return isBalanced;
      }
        public int getDepth(TreeNode root) {
        if (root == null)
  			return 0;
  		int left = getDepth(root.left);
  		int right = getDepth(root.right);
  		if (Math.abs(left - right) > 1) {
  			isBalanced = false;
  		}
  		return right > left ? right + 1 : left + 1;
        }
  }
  复制代码

  6.对称二叉树

  标题来自 LeetCode 问题 101：对称二叉树。

  问题描述

  给定一个二叉树，检查它是否是镜像对称的。

  例如，二叉树[1,2,2,3,4,4,3]是对称的。

      1
     / \
    2   2
   / \ / \
  3  4 4  3
  复制代码

  问题分析

  递归比较容易做：对称树相当于左子树及其的右子树。两棵树是对称的，问题就变成了判断两棵树。树是对称的吗？

  代码实现

  class Solution {
      public boolean isSymmetric(TreeNode root) {
          if(root == null) return true;
          //把问题变成判断两棵树是否是对称的
          return isSym(root.left, root.right);
      }
      //判断的是根节点为r1和r2的两棵树是否是对称的
      public boolean isSym(TreeNode r1, TreeNode r2){
          if(r1 == null && r2 == null) return true;
          if(r1 == null || r2 == null) return false;
          //这两棵树是对称需要满足的条件：
          //1.俩根节点相等。 2.树1的左子树和树2的右子树，树2的左子树和树1的右子树都得是对称的
          return r1.val == r2.val && isSym(r1.left, r2.right) 
                              && isSym(r1.right, r2.left);
      }
  }
  复制代码

  7.重建二叉树

  标题来自建志的建议：重建二叉树。

  问题描述

  根据二叉树的前序遍历和顺序遍历的结果重建二叉树。我们假设输入的预序爬取和中序爬取的结果不包含重复的数字。

  preorder = [3,9,20,15,7]
  inorder =  [9,3,15,20,7]
  复制代码

  问题分析

  先序遍历的第一个值是根节点的值。使用该值将顺序遍历的结果分成两部分。左边部分是树的左子树的有序遍历，右边部分是树。按顺序遍历右子树的结果。

  动画说明

  

  代码实现

  // 缓存中序遍历数组每个值对应的索引
  private Map<Integer, Integer> indexForInOrders = new HashMap<>();
  
  public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
      for (int i = 0; i < in.length; i++)
          indexForInOrders.put(in[i], i);
      return reConstructBinaryTree(pre, 0, pre.length - 1, 0);
  }
  
  private TreeNode reConstructBinaryTree(int[] pre, int preL, int preR, int inL) {
      if (preL > preR)
          return null;
      TreeNode root = new TreeNode(pre[preL]);
      int inIndex = indexForInOrders.get(root.val);
      int leftTreeSize = inIndex - inL;
      root.left = reConstructBinaryTree(pre, preL + 1, preL + leftTreeSize, inL);
      root.right = reConstructBinaryTree(pre, preL + leftTreeSize + 1, preR, inL + leftTreeSize + 1);
      return root;
  }

  作者：程序员吴哥
  链接：https://juejin.im/post/5c8fa09bf265da60f30d3ggfb3版权归作者所有。商业转载请联系作者获得许可。非商业转载请注明来源。