几道和「二叉树」有关的算法面试题

￡神魔★判官ぃ 2022-03-06 02:26 251阅读 0赞

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

二叉树的详细讲解请戳这：[懵逼树上懵逼果：学习二分搜索树][Link 1]

## 1. 二叉树的前序遍历 ##

题目来源于 LeetCode 第 144 号问题：二叉树的前序遍历。

### 题目描述 ###

给定一个二叉树，返回它的 前序 遍历。

### 题目解析 ###

用**栈(Stack)**的思路来处理问题。

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

*  把根节点push到栈中
 *  循环检测栈是否为空，若不空，则取出栈顶元素，保存其值
 *  看其右子节点是否存在，若存在则push到栈中
 *  看其左子节点，若存在，则push到栈中。

### 动画描述 ###

![640?wx\_fmt=gif][640_wx_fmt_gif] 二叉树的前序遍历

### 代码实现 ###

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 号问题：二叉树的中序遍历。

### 题目描述 ###

给定一个二叉树，返回它的 中序 遍历。

### 题目解析 ###

用**栈(Stack)**的思路来处理问题。

中序遍历的顺序为**左-根-右**，具体算法为：

*  从根节点开始，先将根节点压入栈
 *  然后再将其所有左子结点压入栈，取出栈顶节点，保存节点值
 *  再将当前指针移到其右子节点上，若存在右子节点，则在下次循环时又可将其所有左子结点压入栈中

### 动画描述 ###

![640?wx\_fmt=gif][640_wx_fmt_gif 1] 二叉树的中序遍历

### 代码实现 ###

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 号问题：二叉树的后序遍历。

### 题目描述 ###

给定一个二叉树，返回它的 后序 遍历。

### 题目解析 ###

用**栈(Stack)**的思路来处理问题。

后序遍历的顺序为**左-右-根**，具体算法为：

*  先将根结点压入栈，然后定义一个辅助结点head
 *  while循环的条件是栈不为空
 *  在循环中，首先将栈顶结点t取出来
 *  如果栈顶结点没有左右子结点，或者其左子结点是head，或者其右子结点是head的情况下。我们将栈顶结点值加入结果res中，并将栈顶元素移出栈，然后将head指向栈顶元素
 *  否则的话就看如果右子结点不为空，将其加入栈
 *  再看左子结点不为空的话，就加入栈

### 动画描述 ###

![640?wx\_fmt=gif][640_wx_fmt_gif 2] 二叉树的后序遍历

### 代码实现 ###

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

返回其层次遍历结果：

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

### 题目解析 ###

该问题需要用到**队列**。

*  建立一个queue
 *  先把根节点放进去，这时候找根节点的左右两个子节点
 *  去掉根节点，此时queue里的元素就是下一层的所有节点
 *  用for循环遍历，将结果存到一个一维向量里
 *  遍历完之后再把这个一维向量存到二维向量里
 *  以此类推，可以完成层序遍历

### 动画描述 ###

![640?wx\_fmt=gif][640_wx_fmt_gif 3] 二叉树的层序遍历

### 代码实现 ###

public List<List<Integer>> levelOrder(TreeNode root) {
        
        if(root == null)
            return new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while(!queue.isEmpty()){
        
            int count = queue.size();
            List<Integer> list = new ArrayList<Integer>();
            while(count > 0){
        
                TreeNode node = queue.poll();
                list.add(node.val);
                if(node.left != null)
                    queue.add(node.left);
                if(node.right != null)
                    queue.add(node.right);
                count--;
            }
            res.add(list);
        }
        return res;
    }

## 5. 平衡二叉树 ##

题目来源于 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. 重建二叉树 ##

题目来源于 剑指 offer ：重建二叉树。

### 题目描述 ###

根据二叉树的前序遍历和中序遍历的结果，重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

preorder = [3,9,20,15,7]
    inorder =  [9,3,15,20,7]

### 题目解析 ###

前序遍历的第一个值为根节点的值，使用这个值将中序遍历结果分成两部分，左部分为树的左子树中序遍历结果，右部分为树的右子树中序遍历的结果。

### 动画描述 ###

![640?wx\_fmt=gif][640_wx_fmt_gif 4] 动画来源于 CS-Notes

### 代码实现 ###

// 缓存中序遍历数组每个值对应的索引
    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;
    }

**推荐阅读：**

[几道和「堆栈、队列」有关的面试算法题][Link 2]

[几道和「哈希表」有关的面试算法题][Link 3]

## [链表算法面试问题？看我就够了！][Link 4] ##

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

**欢迎关注这个会做动画的程序员?**

喜欢就点击“好看”吧！

[640_wx_fmt_jpeg]: /images/20220306/de7d85a418e34fe48db22947ffe9d4f4.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484198&idx=1&sn=7c6900bbb6798dc3cc5f10e820ca25a3&chksm=fa0e6ca7cd79e5b11dc1951324039257def9dd83402840e62201ef3dd4e60dcd297314fed34a&scene=21#wechat_redirect
[640_wx_fmt_gif]: /images/20220306/1131ed060d484fe6b53a4b0130ac7bcf.png
[640_wx_fmt_gif 1]: /images/20220306/8af7993084c04e26a08af045d0672dea.png
[640_wx_fmt_gif 2]: /images/20220306/f390b7ecc0ba489fb256e632f0f27d65.png
[640_wx_fmt_gif 3]: /images/20220306/bf6bed9c4abb4a9d9d3b404d03908209.png
[640_wx_fmt_gif 4]: /images/20220306/970a3178537f452d86302000f1417548.png
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484846&idx=2&sn=e508da06e9f7a0b3d00db5415d7ce622&chksm=fa0e6a2fcd79e3397fe8083f9493ae639f47c9448ac2a0026026494d098c47ecc6e08f1f8e28&scene=21#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484977&idx=1&sn=f4a6148480555e3cca83231ac1df8d02&chksm=fa0e69b0cd79e0a686e31c547fc783eb9663d9fe19cc95ecd524e9f8f7e0d4a168945f8755e5&scene=21#wechat_redirect
[Link 4]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484830&idx=1&sn=9d24fc787da4b49b82ac01c7f8de257b&chksm=fa0e6a1fcd79e309a2e7f3e09ec9913a55f1c077287c907f13528578b7785831a2effb3104e0&scene=21#wechat_redirect
[640_wx_fmt_jpeg 1]: /images/20220306/ab53e42f5f6e414f8172416906c4e930.png