二叉树面试题刷题模板[终极版]

心已赠人 2022-12-22 08:59 98阅读 0赞

### 文章目录 ###

*  递归
 *   *  树结构
     *  二叉树的最大深度
     *   *  后序递归
     *  二叉树最小深度
     *   *  后序递归
     *  二叉树的直径
     *   *  后序递归
     *  平衡二叉树
     *   *  后序递归
     *  小总结
     *  对称的二叉树
     *   *  递归解法
     *  二叉树的镜像
     *   *  后序递归
     *  树的子结构
     *   *  递归解法
     *  二叉搜索树的最近公共祖先
     *   *  前序递归
     *  二叉树的最近公共祖先
     *   *  前序递归
     *  二叉搜索树的第k大节点
     *   *  中序递归
     *  二叉树中和为某一值的路径
     *   *  前序递归
     *  538. 把二叉搜索树转换为累加树
     *   *  类中序递归
     *  669. 修剪二叉搜索树
     *   *  前序递归
     *  找树左下角的值
     *   *  前序递归遍历
     *  左叶子之和
     *   *  递归遍历
     *  最长同值路径
     *   *  后序递归
     *  二叉树中第二小的节点
     *   *  递归遍历
     *  572. 另一个树的子树
     *   *  前序递归
     *  合并二叉树
     *   *  前序递归
     *  路径总和
     *   *  前序递归
     *  113. 路径总和 II
     *   *  前序递归
     *  路径总和 III
     *   *  前序递归
     *  打家劫舍 III
     *   *  递归遍历
     *  剑指 Offer 07. 重建二叉树
     *   *  递归遍历
     *  剑指 Offer 37. 序列化二叉树
     *   *  递归遍历
 *  层序遍历
 *   *  层序遍历模板
     *  剑指 Offer 32 - I. 从上到下打印二叉树
     *  求二叉树深度
     *  剑指 Offer 32 - II. 从上到下打印二叉树 II
     *  剑指 Offer 32 - III. 从上到下打印二叉树 III
     *  二叉树的层平均值
     *  对称的二叉树
 *  二叉树非递归前中后序遍历
 *   *  前序遍历
     *  中序遍历
     *  后序遍历

# 递归 #

几乎所有树的题都可以用递归解决，可以用递归解决的问题，也就可以用迭代的方法解决，因为递归调用就是一个出栈入栈的问题。

## 树结构 ##

public class TreeNode {
        
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
         val = x; }
    }

## 二叉树的最大深度 ##

[剑指 Offer 55 - I. 二叉树的深度][Offer 55 - I.]

### 后序递归 ###

求出左右子树的深度，根的深度就是左子树深度和右子树深度中的最大值加1.

class Solution {
        
        public int maxDepth(TreeNode root) {
        
            if (root == null) {
        
                return 0;
            }
            int leftDepth = maxDepth(root.left);
            int rightDepth = maxDepth(root.right);
            return 1 + Math.max(leftDepth, rightDepth);
        }
    }

## 二叉树最小深度 ##

[111. 二叉树的最小深度][111.]

### 后序递归 ###

求出左右子树的深度，根的深度就是左子树深度和右子树深度中的最小值加1。这里要注意左右子树深度为0的情况。

class Solution {
        
        public int minDepth(TreeNode root) {
        
            if (root == null) {
        
                return 0;
            }
            int left = minDepth(root.left);
            int right = minDepth(root.right);
            if (left == 0 || right == 0) {
        
                return left + right + 1;
            }
            return Math.min(left, right) + 1;
        }
    }

## 二叉树的直径 ##

[543. 二叉树的直径][543.]

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

注意：两结点之间的路径长度是以它们之间边的数目表示。

### 后序递归 ###

求出左子树高度和右子树高度的最大值。有没有发现这跟求二叉树的最大深度很相似，这里只是多一个记录左子树高度和右子树高度的最大值而已。

class Solution {
        
        private int max = 0;
        public int diameterOfBinaryTree(TreeNode root) {
        
            depth(root);
            return max;
        }
        private int depth(TreeNode root) {
        
            if (root == null) {
        
                return 0;
            }
            int left = depth(root.left);
            int right = depth(root.right);
            max = Math.max(max, left + right);
            return Math.max(left, right) + 1;
        }
    }

## 平衡二叉树 ##

[剑指 Offer 55 - II. 平衡二叉树][Offer 55 - II.]

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

### 后序递归 ###

这题不用我说的了吧，是不是跟上面三道题出奇的相似，只是把求二叉树直径变成了平衡二叉树的判断。

class Solution {
        
        private boolean flag = true;
        public boolean isBalanced(TreeNode root) {
        
            maxDepth(root);
            return flag;
        }
        private int maxDepth(TreeNode root) {
        
            if (root == null) {
        
                return 0;
            }
            int leftDepth = maxDepth(root.left);
            int rightDepth = maxDepth(root.right);
            if (Math.abs(leftDepth - rightDepth) > 1) {
        
                flag = false;
            }
            return 1 + Math.max(leftDepth, rightDepth);
        }
    }

## 小总结 ##

上面四道题其实就是二叉树的递归遍历，前、中和后序递归遍历的模板如下：

public void dfs(TreeNode root) {
        
            if (root == null) {
        
                return;
            }
            // 代码写在这里就是前序遍历
            dfs(root.left);
            // 代码写在这里就是中序遍历
            dfs(root.right);
            // 代码写在这里就是后序遍历
        }

## 对称的二叉树 ##

[剑指 Offer 28. 对称的二叉树][Offer 28.]

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

### 递归解法 ###

这里需要用根节点的左右孩子进行递归，因为这样比较方便判断，左右孩子是否符合条件。

class Solution {
        
        public boolean isSymmetric(TreeNode root) {
        
            if (root == null) {
        
                return true;
            }
            return isSymmetric(root.left, root.right);
        }
        private boolean isSymmetric(TreeNode t1, TreeNode t2) {
        
            if (t1 == null && t2 == null) {
        
                return true;
            }
            if (t1 == null || t2 == null) {
        
                return false;
            }
            if (t1.val != t2.val) {
        
                return false;
            }
            return isSymmetric(t1.left, t2.right) && isSymmetric(t1.right, t2.left);
        }
    }

## 二叉树的镜像 ##

[剑指 Offer 27. 二叉树的镜像][Offer 27.]

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

### 后序递归 ###

左孩子和右孩子进行递归交换，注意先把左孩子或者右孩子保存起来才能交换。很多朋友，表示理解不了递归，其实可以找一段视频看一下，每次入栈出栈是怎么回事，再把这里的题刷一刷，搞定递归不是问题。

class Solution {
        
        public TreeNode mirrorTree(TreeNode root) {
        
            if (root == null) {
        
                return null;
            }
            TreeNode temp = root.right;
            root.right = mirrorTree(root.left);
            root.left = mirrorTree(temp);
            return root;
        }
    }

## 树的子结构 ##

[剑指 Offer 26. 树的子结构][Offer 26.]

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

### 递归解法 ###

class Solution {
        
        public boolean isSubStructure(TreeNode A, TreeNode B) {
        
            return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
        }
        boolean recur(TreeNode A, TreeNode B) {
        
            if (B == null) {
        
                return true;
            }
            if (A == null || A.val != B.val) {
        
                return false;
            }
            return recur(A.right, B.right) && recur(A.left, B.left);
        }
    }

## 二叉搜索树的最近公共祖先 ##

[剑指 Offer 68 - I. 二叉搜索树的最近公共祖先][Offer 68 - I.]

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = \[6,2,8,0,4,7,9,null,null,3,5\]

### 前序递归 ###

这题应该是比较简单的，拿root的值跟p、q的值对比，如果`val < p.val && val < q.val`说明，p、q最近公共祖先在右子树，如此递归轻松解决。

class Solution {
        
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
            int val = root.val;
            if (val < p.val && val < q.val) {
        
                return lowestCommonAncestor(root.right, p, q);
            }
            if (val > p.val && val > q.val) {
        
                return lowestCommonAncestor(root.left, p, q);
            }
            return root;
        }
    }

## 二叉树的最近公共祖先 ##

[剑指 Offer 68 - II. 二叉树的最近公共祖先][Offer 68 - II.]

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

### 前序递归 ###

看到这道题是不是有点懵逼，没有二叉搜索树的性质了，普通的二叉树怎么求最近公共祖先？仔细思考一下，其实就是三种情况，要么q是p的祖先，要么p是q的祖先，要么q和p是某一个节点的左右子树里面的节点。基于上面的分析，不难想到，我们依然可以通过递归遍历进行对比判断，代码如下：

class Solution {
        
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
            if (root == null || root == p || root == q) {
        
                return root;
            }
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            // 下面代码意思是，如果left为null，父节点为right;如果right为null,则父节点为left；如果
            // left和right都不为null，说明父节点就是当前的root。
            return left == null ? right : right == null ? left : root;
        }
    }

## 二叉搜索树的第k大节点 ##

[剑指 Offer 54. 二叉搜索树的第k大节点][Offer 54. _k]

给定一棵二叉搜索树，请找出其中第k大的节点。

### 中序递归 ###

利用二叉搜索树的性质，其中序遍历是递增有序的，所有我们给他来个中序遍历就搞定了。这也就是利用上面的递归遍历树的模板，在中间添一点代码就AC。

class Solution {
        
        int k, res;
        public int kthLargest(TreeNode root, int k) {
        
            this.k = k;
            dfs(root);
            return res;
        }
        private void dfs(TreeNode root) {
        
            if (root == null) {
        
                return;
            }
            dfs(root.right);
            if (k == 0) {
        
                return;
            }
            if (--k == 0) {
        
                res = root.val;
            }
            dfs(root.left);
        }
    }

## 二叉树中和为某一值的路径 ##

[剑指 Offer 34. 二叉树中和为某一值的路径][Offer 34.]

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

### 前序递归 ###

这依然是递归遍历树，先序遍历，满足条件就加入结果，不满足就继续递归。递归最后需要把最后一个节点值出栈，因为已经用完了，不需要这个值了。这里用双端队列模拟栈，因为stack是遗留类了不推荐使用，小技巧就是每次都入栈到尾部，这样从根节点开始就是有序的。

class Solution {
        
        List<List<Integer>> res = new LinkedList<>();
        public List<List<Integer>> pathSum(TreeNode root, int sum) {
        
            Deque<Integer> stack = new LinkedList<>();
            dfs(root, stack, sum);
            return res;
        }
        private void dfs(TreeNode root, Deque<Integer> stack, int sum) {
        
            if (root == null) {
        
                return;
            }
            stack.offerLast(root.val);
            if (root.val == sum && root.left == null && root.right == null) {
        
                res.add(new LinkedList<>(stack));
                stack.pollLast();
                return;
            }
            if (root.left != null) {
        
                dfs(root.left, stack, sum - root.val);
            }
            if (root.right != null) {
        
                dfs(root.right, stack, sum - root.val);
            }
            stack.pollLast();
        }
    }

## 538. 把二叉搜索树转换为累加树 ##

[538. 把二叉搜索树转换为累加树][538.]

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

节点的左子树仅包含键 小于 节点键的节点。  
节点的右子树仅包含键 大于 节点键的节点。  
左右子树也必须是二叉搜索树

### 类中序递归 ###

又是递归遍历，先遍历右孩子，再遍历根节点，然后遍历左孩子。

## 669. 修剪二叉搜索树 ##

[669. 修剪二叉搜索树][669.]

给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在\[low, high\]中。修剪树不应该改变保留在树中的元素的相对结构（即，如果没有被移除，原有的父代子代关系都应当保留）。 可以证明，存在唯一的答案。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

### 前序递归 ###

*  root.val > high，说明root和root的右孩子都需要删除，所以递归遍历root的左孩子
 *  root.val < low，同理

class Solution {
        
        public TreeNode trimBST(TreeNode root, int low, int high) {
        
            if (root == null) {
        
                return null;
            }
            if (root.val > high) {
        
                return trimBST(root.left, low, high);
            }
            if (root.val < low) {
        
                return trimBST(root.right, low, high);
            }
            root.left = trimBST(root.left, low, high);
            root.right = trimBST(root.right, low, high);
            return root;
        }
    }

## 找树左下角的值 ##

[513. 找树左下角的值][513.]

给定一个二叉树，在树的最后一行找到最左边的值。

### 前序递归遍历 ###

当`height > max`时，记录高度和当前结点的值，当前结点就是最左结点。

class Solution {
        
        private int max = -1;
        private int result = 0;
        public int findBottomLeftValue(TreeNode root) {
        
            dfs(root, 1);
            return result;
        }
        private void dfs(TreeNode node, int height) {
        
            if (node == null) {
        
                return;
            }
            if (height > max) {
        
                max = height;
                result = node.val;
            }
            dfs(node.left, height + 1);
            dfs(node.right, height + 1);
        }
    }

## 左叶子之和 ##

[404. 左叶子之和][404.]

计算给定二叉树的所有左叶子之和。

### 递归遍历 ###

class Solution {
        
        public int sumOfLeftLeaves(TreeNode root) {
        
            if (root == null) {
        
                return 0;
            }
            if (isLeaf(root.left)) {
        
                return root.left.val + sumOfLeftLeaves(root.right);
            }
            return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
        }
        private boolean isLeaf(TreeNode root) {
        
            if (root == null) {
        
                return false;
            }
            return root.left == null && root.right == null;
        }
    }

## 最长同值路径 ##

[687. 最长同值路径][687.]

给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。

注意：两个节点之间的路径长度由它们之间的边数表示。

### 后序递归 ###

用一个path记录最长同值路径。

class Solution {
        
        private int path = 0;
        public int longestUnivaluePath(TreeNode root) {
        
            dfs(root);
            return path;
        }
        private int dfs(TreeNode root) {
        
            if (root == null) {
        
                return 0;
            }
            int left = dfs(root.left);
            int right = dfs(root.right);
            int leftDepth = root.left != null && root.val == root.left.val ? left + 1 : 0;
            int rightDepth = root.right != null && root.val == root.right.val ? right + 1 : 0;
            path = Math.max(path, leftDepth + rightDepth);
            return Math.max(leftDepth, rightDepth);
        }
    }

## 二叉树中第二小的节点 ##

[671. 二叉树中第二小的节点][671.]

给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 2 或 0。如果一个节点有两个子节点的话，那么这个节点的值不大于它的子节点的值。

给出这样的一个二叉树，你需要输出所有节点中的第二小的值。如果第二小的值不存在的话，输出 -1 。

### 递归遍历 ###

class Solution {
        
        public int findSecondMinimumValue(TreeNode root) {
        
            if (root == null || (root.left == null && root.right == null)) {
        
                return -1;
            }
            int leftVal = root.left.val;
            int rightVal = root.right.val;
            if (leftVal == root.val) {
        
                leftVal = findSecondMinimumValue(root.left);
            }
            if (rightVal == root.val) {
        
                rightVal = findSecondMinimumValue(root.right);
            }
            if (leftVal != -1 && rightVal != -1) {
        
                return Math.min(leftVal, rightVal);
            }
            if (leftVal == -1) {
        
                return rightVal;
            }
            return leftVal;
        }
    }

## 572. 另一个树的子树 ##

[572. 另一个树的子树][572.]

给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

### 前序递归 ###

class Solution {
        
        public boolean isSubtree(TreeNode s, TreeNode t) {
        
            if (s == null) {
        
                return false;
            }
            return dfs(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
        }
        private boolean dfs(TreeNode s, TreeNode t) {
        
            if (s == null && t == null) {
        
                return true;
            }
            if (s == null || t == null || s.val != t.val) {
        
                return false;
            }
            return dfs(s.left, t.left) && dfs(s.right, t.right);
        }
    }

## 合并二叉树 ##

[617. 合并二叉树][617.]

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

### 前序递归 ###

class Solution {
        
        public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        
            if (t1 == null && t2 == null) {
        
                return null;
            }
            if (t1 == null) {
        
                return t2;
            }
            if (t2 == null) {
        
                return t1;
            }
            TreeNode root = new TreeNode(t1.val + t2.val);
            root.left = mergeTrees(t1.left, t2.left);
            root.right = mergeTrees(t1.right, t2.right);
            return root;
        }
    }

## 路径总和 ##

[112. 路径总和][112.]

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

### 前序递归 ###

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

## 113. 路径总和 II ##

[113. 路径总和 II][113. _ II]

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

**说明:** 叶子节点是指没有子节点的节点。

### 前序递归 ###

没啥好说的，前序递归遍历即可。

class Solution {
        
        List<List<Integer>> res = new LinkedList<>();
        public List<List<Integer>> pathSum(TreeNode root, int sum) {
        
            dfs(root, new LinkedList<Integer>(), sum);
            return res;
        }
        private void dfs(TreeNode root, Deque<Integer> list, int sum) {
        
            if (root == null) {
        
                return;
            }
            list.offerLast(root.val);
            if (root.left == null && root.right == null && root.val == sum) {
        
                res.add(new LinkedList<Integer>(list));
                list.pollLast();
                return;
            }
            dfs(root.left, list, sum - root.val);
            dfs(root.right, list, sum - root.val);
            list.pollLast();
        }
    }

## 路径总和 III ##

[437. 路径总和 III][437. _ III]

给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

二叉树不超过1000个节点，且节点数值范围是 \[-1000000,1000000\] 的整数。

### 前序递归 ###

跟\[572. 另一个树的子树\](\#572. 另一个树的子树)类似，可以对比一下。

class Solution {
        
        public int pathSum(TreeNode root, int sum) {
        
            if (root == null) {
        
                return 0;
            }
            int ret = dfs(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
            return ret;
        }
        private int dfs(TreeNode root, int sum) {
        
            if (root == null) {
        
                return 0;
            }
            int ret = 0;
            if (root.val == sum) {
        
                ret++;
            }
            ret += dfs(root.left, sum - root.val) + dfs(root.right, sum - root.val);
            return ret;
        }
    }

## 打家劫舍 III ##

[337. 打家劫舍 III][337. _ III]

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

### 递归遍历 ###

class Solution {
        
        public int rob(TreeNode root) {
        
            if (root == null) {
        
                return 0;
            }
            int var1 = root.val;
            if (root.left != null) {
        
                var1 += rob(root.left.left) + rob(root.left.right);
            }
            if (root.right != null) {
        
                var1 += rob(root.right.left) + rob(root.right.right);
            }
            int var2 = rob(root.left) + rob(root.right);
            return Math.max(var1, var2);
        }
    }

## 剑指 Offer 07. 重建二叉树 ##

[剑指 Offer 07. 重建二叉树][Offer 07.]

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

### 递归遍历 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        private Map<Integer, Integer> indexMap;
        private TreeNode myBuildTree(int[] preorder, int[] inorder, int preorderLeft, int preorderRight, int inorderLeft, int inorderRight) {
        
            if (preorderLeft > preorderRight) {
        
                return null;
            }
            // 前序遍历中的第一个节点就是根节点
            // 在中序遍历中定位根节点
            int inorderRoot = indexMap.get(preorder[preorderLeft]);
            TreeNode root = new TreeNode(preorder[preorderLeft]);
            // 得到左子树中的节点数目
            int sizeLeftSubtree = inorderRoot - inorderLeft;
            // 递归地构造左子树，并连接到根节点
            // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
            root.left = myBuildTree(preorder, inorder, preorderLeft + 1, preorderLeft + sizeLeftSubtree, inorderLeft, inorderRoot - 1);
            root.right = myBuildTree(preorder, inorder, preorderLeft + sizeLeftSubtree + 1, preorderRight, inorderRoot + 1, inorderRight);
            return root;
        }
        public TreeNode buildTree(int[] preorder, int[] inorder) {
        
            int n = preorder.length;
            indexMap = new HashMap<>();
            // 构造哈希映射，帮助我们快速定位根节点
            for (int i = 0; i < n; i++) {
        
                indexMap.put(inorder[i], i);
            }
            return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
        } 
    }

## 剑指 Offer 37. 序列化二叉树 ##

[剑指 Offer 37. 序列化二叉树][Offer 37.]

请实现两个函数，分别用来序列化和反序列化二叉树。

示例: 
    
    你可以将以下二叉树：
    
        1
       / \
      2   3
         / \
        4   5
    
    序列化为 "[1,2,3,null,null,4,5]"

### 递归遍历 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Codec {
        
        private StringBuilder serialize(TreeNode root, StringBuilder sb) {
        
            if (root == null) {
        
                sb.append("None,");
            } else {
        
                sb.append(String.valueOf(root.val) + ",");
                sb = serialize(root.left, sb);
                sb = serialize(root.right, sb);
            }
            return sb;
        }
    
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
        
            return serialize(root, new StringBuilder()).toString();
        }
    
        private TreeNode deserialize(List<String> list) {
        
            if (list.get(0).equals("None")) {
        
                list.remove(0);
                return null;
            }
            TreeNode root = new TreeNode(Integer.valueOf(list.get(0)));
            list.remove(0);
            root.left = deserialize(list);
            root.right = deserialize(list);
            return root;
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
        
            String[] array = data.split(",");
            List<String> list = new LinkedList<String>(Arrays.asList(array));
            return deserialize(list);
        }
    }
    
    // Your Codec object will be instantiated and called as such:
    // Codec codec = new Codec();
    // codec.deserialize(codec.serialize(root));

# 层序遍历 #

层序遍历顾名思义就是对树一层一层的遍历，显而易见把节点放入队列中，然后依次出队列就是层序遍历结果。

## 层序遍历模板 ##

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public List<Integer> levelOrder(TreeNode root) {
        
            if (root == null) {
        
                return new int[0];
            }
            Queue<TreeNode> queue = new LinkedList<>();
            List<Integer> list = new ArrayList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
        
                TreeNode node = queue.poll();
                // 可以进行一些操作
                list.add(node.val);
                if (node.left != null) {
        
                    queue.offer(node.left);
                }
                if (node.right != null) {
        
                    queue.offer(node.right);
                }
                // 可以进行一些操作
            }
            return list;
        }
    }

## 剑指 Offer 32 - I. 从上到下打印二叉树 ##

[剑指 Offer 32 - I. 从上到下打印二叉树][Offer 32 - I.]

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public int[] levelOrder(TreeNode root) {
        
            if (root == null) {
        
                return new int[0];
            }
            Queue<TreeNode> queue = new LinkedList<>();
            List<Integer> list = new ArrayList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
        
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) {
        
                    queue.offer(node.left);
                }
                if (node.right != null) {
        
                    queue.offer(node.right);
                }
            }
            int[] res = new int[list.size()];
            for (int i = 0; i < list.size(); i++) {
        
                res[i] = list.get(i);
            }
            return res;
        }
    }

## 求二叉树深度 ##

上面二叉树的最大深度也可以用层序遍历解决

class Solution {
        
        public int maxDepth(TreeNode root) {
        
            if (root == null) {
        
                return 0;
            }
            Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
            queue.offer(new Pair(root, 1));
            int maxDepth = Integer.MIN_VALUE;
            while (!queue.isEmpty()) {
        
                Pair<TreeNode, Integer> pair = queue.poll();
                TreeNode node = pair.getKey();
                int currentDepth = pair.getValue();
                if (node != null) {
        
                    maxDepth = Math.max(currentDepth, maxDepth);
                    queue.offer(new Pair(node.left, currentDepth + 1));
                    queue.offer(new Pair(node.right, currentDepth + 1));
                }
            }
            return maxDepth;
        }
    }

## 剑指 Offer 32 - II. 从上到下打印二叉树 II ##

[剑指 Offer 32 - II. 从上到下打印二叉树 II][Offer 32 - II. _ II]

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

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

## 剑指 Offer 32 - III. 从上到下打印二叉树 III ##

[剑指 Offer 32 - III. 从上到下打印二叉树 III][Offer 32 - III. _ III]

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public List<List<Integer>> levelOrder(TreeNode root) {
        
            List<List<Integer>> res = new ArrayList<>();
            if (root == null) {
        
                return res;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
        
                int size = queue.size();
                List<Integer> list = new ArrayList<>();
                for (int i = 0; i < size; i++) {
        
                    TreeNode node = queue.poll();
                    list.add(node.val);
                    if (node.left != null) {
        
                        queue.add(node.left);
                    }
                    if (node.right != null) {
        
                        queue.add(node.right);
                    }
                }
                // 奇数时，翻转list
                if (res.size() % 2 == 1) {
        
                    Collections.reverse(list);
                }
                res.add(list);
            }
            return res;
        }
    }

## 二叉树的层平均值 ##

[637. 二叉树的层平均值][637.]

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组.

class Solution {
        
        public List<Double> averageOfLevels(TreeNode root) {
        
            List<Double> res = new ArrayList<>();
            if (root == null) {
        
                return res;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
        
                double sum = 0;
                int size = queue.size();
                for (int i = 0; i < size; i++) {
        
                    TreeNode node = queue.poll();
                    sum += node.val;
                    if (node.left != null) {
        
                        queue.offer(node.left);
                    }
                    if (node.right != null) {
        
                        queue.offer(node.right);
                    }
                }
                res.add(sum / size);
            }
            return res;
        }
    }

## 对称的二叉树 ##

上面的对称的二叉树层序遍历解法如下

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public boolean isSymmetric(TreeNode root) {
        
            if (root == null) {
        
                return true;
            }
            return isSymmetric(root.left, root.right);
        }
        private boolean isSymmetric(TreeNode t1, TreeNode t2) {
        
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(t1);
            queue.offer(t2);
            while (!queue.isEmpty()) {
        
                t1 = queue.poll();
                t2 = queue.poll();
                if (t1 == null && t2 == null) {
        
                    continue;
                }
                if (t1 == null || t2 == null || t1.val != t2.val) {
        
                    return false;
                }
                queue.offer(t1.left);
                queue.offer(t2.right);
                queue.offer(t1.right);
                queue.offer(t2.left);
            }
            return true;
        }
    }

# 二叉树非递归前中后序遍历 #

上面的二叉树的递归遍历比较简单，下面就来看看二叉树的非递归遍历。

> 用Deque模拟栈，因为stack遗留类，不推荐使用

## 前序遍历 ##

[144. 二叉树的前序遍历][144.]

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

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        public List<Integer> preorderTraversal(TreeNode root) {
        
            List<Integer> res = new ArrayList<>();
            if (root == null) {
        
                return res;
            }
            Deque<TreeNode> stack = new LinkedList<>();
            stack.offerFirst(root);
            while (!stack.isEmpty()) {
        
                TreeNode node = stack.pollFirst();
                res.add(node.val);
                // 先入右孩子，这样的话，左孩子先出栈
                if (node.right != null) {
        
                    stack.offerFirst(node.right);
                }
                if (node.left != null) {
        
                    stack.offerFirst(node.left);
                }
            }
            return res;
        }
    }

## 中序遍历 ##

[94. 二叉树的中序遍历][94.]

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

> 思路：依然是用栈，先将左孩子全部入栈，与前序对比，其实就是改变了结点的入栈顺序。注：有栈为空的情况（没有左孩子），所有循环条件改成node != null || !stack.isEmpty()

class Solution {
        
        public List<Integer> inorderTraversal(TreeNode root) {
        
            List<Integer> res = new ArrayList<>();
            if (root == null) {
        
                return res;
            }
            Deque<TreeNode> stack = new LinkedList<>();
            TreeNode node = root;
            while (node != null || !stack.isEmpty()) {
        
                while (node != null) {
        
                    stack.offerFirst(node);
                    node = node.left;
                }
                node = stack.pollFirst();
                res.add(node.val);
                node = node.right;
            }
            return res;
        }
    }

## 后序遍历 ##

[145. 二叉树的后序遍历][145.]

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

> 后序遍历的倒序就是先访问根节点，然后访问右孩子，最后访问左孩子，所以改一改前序遍历就能得到结果。利用LinkedList的性质，可每次插入到链头，相当于翻转。

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public List<Integer> postorderTraversal(TreeNode root) {
        
            if (root == null) {
        
                return new LinkedList<>();
            }
            LinkedList<Integer> res = new LinkedList<>();
            Deque<TreeNode> stack = new LinkedList<>();
            stack.addFirst(root);
            while(!stack.isEmpty()) {
        
                TreeNode node = stack.removeFirst();
                // 利用LinkedList的性质，可每次插入到链头，相当于翻转。
                res.addFirst(node.val);
                if (node.left != null) {
        
                    stack.addFirst(node.left);
                }
                if (node.right != null) {
        
                    stack.addFirst(node.right);
                }
            }
            return res;
        }
    }

**欢迎关注我的公众号呦，率先更新内容，并且后续还有一些源码级的免费教程推出。**

![gzh.jpg][]

[Offer 55 - I.]: https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/
[111.]: https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
[543.]: https://leetcode-cn.com/problems/diameter-of-binary-tree/
[Offer 55 - II.]: https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/
[Offer 28.]: https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/
[Offer 27.]: https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/
[Offer 26.]: https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/
[Offer 68 - I.]: https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/
[Offer 68 - II.]: https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/
[Offer 54. _k]: https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/
[Offer 34.]: https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/
[538.]: https://leetcode-cn.com/problems/convert-bst-to-greater-tree/
[669.]: https://leetcode-cn.com/problems/trim-a-binary-search-tree/
[513.]: https://leetcode-cn.com/problems/find-bottom-left-tree-value/
[404.]: https://leetcode-cn.com/problems/sum-of-left-leaves/
[687.]: https://leetcode-cn.com/problems/longest-univalue-path/
[671.]: https://leetcode-cn.com/problems/second-minimum-node-in-a-binary-tree/
[572.]: https://leetcode-cn.com/problems/subtree-of-another-tree/
[617.]: https://leetcode-cn.com/problems/merge-two-binary-trees/
[112.]: https://leetcode-cn.com/problems/path-sum/
[113. _ II]: https://leetcode-cn.com/problems/path-sum-ii/
[437. _ III]: https://leetcode-cn.com/problems/path-sum-iii/
[337. _ III]: https://leetcode-cn.com/problems/house-robber-iii/
[Offer 07.]: https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/
[Offer 37.]: https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof/
[Offer 32 - I.]: https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/
[Offer 32 - II. _ II]: https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/
[Offer 32 - III. _ III]: https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/
[637.]: https://leetcode-cn.com/problems/average-of-levels-in-binary-tree/
[144.]: https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
[94.]: https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
[145.]: https://leetcode-cn.com/problems/binary-tree-postorder-traversal/
[gzh.jpg]: /images/20221120/57ccacc2f73445908396e75ffb59e567.png