二叉树的操作及常见面试题

文章目录

前言

上一篇博主归纳了一下二叉树的基本概念以及性质：

二叉树的概念及性质

本文将附上博主自己手动实现的二叉树常见的各种操作以及归纳总结一下常见的基础面试题。

一、四种遍历方式

二叉树额所有问题最终都是四种遍历方式的衍生问题。

前、中、后序遍历为深度优先遍历（DFS），借助“栈”结构

如图：

1.前序遍历：

ABDEGHCF

先访问根节点，然后递归访问左子树，再递归访问右子树，根左右

递归写法：

publicclassPreorderTraversal{List<Integer> ret =newArrayList<>();publicList<Integer>preorderTraversal(TreeNode root){if(root==null){return ret;}
        ret.add(root.val);preorderTraversal(root.left);preorderTraversal(root.right);return ret;}}

迭代写法：

publicclassPreorder{List<Integer> list =newArrayList<>();Deque<TreeNode> stack =newLinkedList<>();//借助辅助栈publicList<Integer>preorder(TreeNode root){if(root ==null){return list;}TreeNode cur = root;while(!stack.isEmpty()|| cur!=null){//右边这个条件是防止弹出根节点后，右子树还有结点的情况while(cur!=null){
                stack.push(cur);
                list.add(cur.val);
                cur = cur.left;}// 走到这里的时候左子树已经走到了最左下，该弹出最坐下结点，开始访问右子树了
            cur=stack.pop();
            cur = cur.right;}return list;}}

2.中序遍历：

DBGHEACF

先递归左子树，再根，最后递归右子树，左根右 => 先一路向左走到根儿~’

递归写法：

publicclassInorderTraversal{List<Integer> ret =newArrayList<>();publicList<Integer>inorderTraversal(TreeNode root){if(root==null){return ret;}inorderTraversal(root.left);
        ret.add(root.val);inorderTraversal(root.right);return ret;}}

迭代写法：

publicclassInorderTraversal{publicList<Integer>inorder(TreeNode root){List<Integer> list =newArrayList<>();Deque<TreeNode> stack =newLinkedList<>();if(root ==null){return list;}TreeNode cur = root;while(!stack.isEmpty()|| cur!=null){while(cur!=null){
                stack.push(cur);
                cur = cur.left;}
            cur = stack.pop();
            list.add(cur.val);
            cur = cur.right;}return list;}}

3.后序遍历：

DHGEBFCA

先递归左子树再递归右子树，最后根先一路向左走到根儿~~

递归写法：

publicclassPostorderTraversal{List<Integer> ret=newArrayList<>();publicList<Integer>postorderTraversal(TreeNode root){if(root==null){return ret;}postorderTraversal(root.left);postorderTraversal(root.right);
        ret.add(root.val);return ret;}}

迭代写法：

publicclassPostorder{publicList<Integer>postorder(TreeNode root){List<Integer> res =newArrayList<Integer>();if(root ==null){return res;}Deque<TreeNode> stack =newLinkedList<TreeNode>();TreeNode prev =null;while(root !=null||!stack.isEmpty()){while(root !=null){
                stack.push(root);
                root = root.left;}
            root = stack.pop();/**
             * 前面都一样走到最左边，后面加个if判断：每次弹栈就判断当前结点是否应该处理结束，若右子树为空或者右子树处理过了，那就处理当前
             */if(root.right ==null|| root.right == prev){
                res.add(root.val);//当前root结点就是已经处理结束的结点
                prev = root;//所以 prev指向了最新的处理结束的结点，以前的不管了反正都结束了
                root =null;}else{//否则，把当前结点压回栈中
                stack.push(root);
                root = root.right;}}return res;}}

层序遍历为广度优先遍历（BFS），借助队列结构

4.层序遍历：

从二叉树的第一层开始一层层向下遍历，每一层由左至右开始遍历

ABCDEFGH

publicvoidlevelOrder(TreeNode<E> root){Deque<TreeNode<E>> queue =newLinkedList<>();
        queue.offer(root);// 循环的终止条件就是队列为空while(!queue.isEmpty()){// 取出当前层的节点个数，每当进行下一次遍历的时候，队列中就存储了该层的所有元素int n = queue.size();for(int i =0; i < n; i++){TreeNode<E> node = queue.poll();System.out.print(node.val +" ");if(node.left !=null){
                    queue.offer(node.left);}if(node.right !=null){
                    queue.offer(node.right);}}}}

递归把握语义，巧妙使用递归函数的作用帮助我们辅助解决问题。

注意事项：

1.先序遍历的第一个结果一定是当前二叉树的根节点
2.中序遍历左子树的结果一定再根节点左侧，右子树的遍历结果在根节点右侧
3.后序遍历的最后一个结果是当前二叉树的根节点，将后序遍历的结果集reverse得到一个先序遍历的镜像结果集 “根右左”

二、二叉树的基本操作

2.1 统计二叉树的结点个数

递归：

publicintgetNodes(TreeNode<?> root){return root ==null?0:1+getNodes(root.left)+getNodes(root.right);}

非递归：

publicintgetNodesNonRecursion(TreeNode<?> root){if(root ==null){return0;}Deque<TreeNode<?>> queue =newLinkedList<>();
        queue.offer(root);int num =0;while(!queue.isEmpty()){TreeNode temp = queue.poll();
            num++;if(temp.left !=null){
                queue.offer(temp.left);}if(temp.right !=null){
                queue.offer(temp.right);}}return num;}

2.2 统计二叉树的叶子结点个数

总叶子结点个数 = 左树中的叶子结点个数 + 右树中的叶子结点个数

代码如下：

publicintgetLeafNodes(TreeNode<?> root){// 1.边界if(root ==null){return0;}if(root.left ==null&& root.right ==null){// 只有root,root就是一个叶子结点return1;}// 此时root不为空，也有子树，总叶子结点个数 = 左树中的叶子结点个数 + 右树中的叶子结点个数returngetLeafNodes(root.left)+getLeafNodes(root.right);}

2.3 求二叉树第K层节点个数

求以root为根的第k层结点个数 = 以root.left为根的第k - 1层结点个数 + 以root.right为根的第k - 1层结点个数

代码如下：

/**
     * 传入一颗以root为根的二叉树，就能求出第k层的节点个数 k <= height(root)
     *
     * @return
     */publicintgetKLevelNodes(TreeNode root,int k){// 1.边界条件if(root ==null|| k <=0){return0;}if(k ==1){return1;}// 求以root为根的第k层结点个数 = 以root.left为根的第k - 1层结点个数 + 以root.right为根的第k - 1层结点个数returngetKLevelNodes(root.left, k -1)+getKLevelNodes(root.right, k -1);}

2.4 求二叉树的高度

当前树高等于1+左右子树中的最大树高

代码如下：

/**
     * 传入一颗以root为根的二叉树，就能求出该树的高度是多少
     *
     * @param root
     * @return
     */publicintheight(TreeNode root){if(root ==null){return0;}return1+Math.max(height(root.left),height(root.right));}

2.5 判断一棵树中是否包含指定的值

代码如下：

/**
     * 判断以root为根的二叉树中是否包含指定值val
     *
     * @param root
     * @param val
     * @return
     */publicbooleancontains(TreeNode<E> root,E val){if(root ==null){returnfalse;}if(root.val.equals(val)){returntrue;}// 继续在左子树和右子树中寻找是否包含指定值returncontains(root.left, val)||contains(root.right, val);}

三、二叉树的基础面试题

3.1 相同的树

思路：

相同的树就是当前结点相同并且其左右子树的结点也相同，递归实现十分容易。

代码如下：

/**
 * 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;
 *     }
 * }
 */classSolution{publicbooleanisSameTree(TreeNode p,TreeNode q){if(p==null){if(q==null){returntrue;}returnfalse;}if(q==null){if(p==null){returntrue;}returnfalse;}if(p.val== q.val){return(isSameTree(p.left,q.left))&&(isSameTree(p.right,q.right));}returnfalse;}}

3.2 另一棵树的子树

思路：

本题基于上一题，然后从根节点先序遍历来逐一判断当前结点是否为相同的树。

1. 判断root和subRoot是不是就是相同的树 true
2. root.left或者root.right 中判断是否包含subRoot

判断root中是否包含subRoot => root和subRoot就是相同的树 || root.left中是否包含subRoot || root.right中是否包含subRoot

这三个条件有一个满足，就认为root包含subRoot

代码如下：

publicbooleanisSameTree(TreeNode p,TreeNode q){if(p==null){if(q==null){returntrue;}returnfalse;}if(q==null){if(p==null){returntrue;}returnfalse;}if(p.val== q.val){return(isSameTree(p.left,q.left))&&(isSameTree(p.right,q.right));}returnfalse;}publicbooleanisSubtree(TreeNode root,TreeNode subRoot){// 边界if(root ==null&& subRoot ==null){returntrue;}if(root ==null|| subRoot ==null){returnfalse;}// 恰好root和subRoot就是相同的树 => trueif(isSameTree(root,subRoot)){returntrue;}if(isSubtree(root.left,subRoot)){returntrue;}if(isSubtree(root.right,subRoot)){returntrue;}returnfalse;//        return isSameTree(root,subRoot) || isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);}

3.3 平衡二叉树

publicinttreeTall(TreeNode root){if(root==null){return0;}return1+Math.max(treeTall(root.left),treeTall(root.right));}publicbooleanisBalanced(TreeNode root){if(root==null){returntrue;}if(Math.abs(treeTall(root.left)-treeTall(root.right))<=1){returnisBalanced(root.left)&&isBalanced(root.right);}returnfalse;}

总结

以上是二叉树的常见操作以及基础面试题，博主之后会更新二叉树的进阶面试题，于💪扣官方给的题解更通俗易懂一点，希望老铁们多多支持，点个关注和赞，感谢！😁😁😁😁