二叉树笔试面试题集合

深藏阁楼爱情的钟 2021-10-01 12:28 345阅读 0赞

#### 二叉树深度 ####

public int TreeDepth(TreeNode root) {
            if(root==null)
                return 0;
            int left=TreeDepth(root.left)+1;
            int right=TreeDepth(root.right)+1;
            return Math.max(left,right);
        }

#### 判断平衡二叉树 ####

一种方法 可以利用求二叉树深度，从根节点开始递归。再求左右深度进行比较。最后求到叶子节点。但是会重复遍历。  
另外一种方法可以利用后序遍历思路。当遍历根结点时左右子树已经进行了判断，不会有重复遍历的情况。

public class Solution {
        private boolean isBalanced=true;
        public boolean IsBalanced_Solution(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;
        }
    
    }

#### 判断是否是二叉搜索树的后序遍历序列 ####

如数组\{5,7,6,9,11,10,8\} 是二叉搜索树后序遍历序列。发现根节点8，576小于8，是8左子树，91110大于8是右子树，而6又是左子树根节点，10是右子树根节点，发现是递归问题  
方法：从前往后遍历，大于根节点时，为右子树。遍历右子树节点，如果右子树中有节点值小于根节点，则返回false。对左子树右子树进行递归判断。

public boolean judge(int[] a,int start,int end){
            if(start>=end)
                return true;
            int i=start;
            while(i<end&&a[i]<a[end]){
                i++;
            }
            for(int j=i;j<end;j++){
                if(a[j]<a[end])
                    return false;
            }
            return judge(a,start,i-1)&&judge(a,i,end-1);
        }

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

题目描述：输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。  
DFS问题，可以用栈也可以用list。

public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
            ArrayList<ArrayList<Integer>> all=new ArrayList<ArrayList<Integer>>();
            if(root==null)
               return all;
            Stack<Integer> stack=new Stack<Integer>();
            FindPath(root, target,stack,all);
            return all;
         }
         
    
         
         void FindPath(TreeNode root,int target,Stack<Integer> stack, ArrayList<ArrayList<Integer>> all){
            if(root==null)
                return;
            if((root.left==null&&root.right==null)&&root.val==target){
                    ArrayList<Integer> list=new ArrayList<>();
                    for(int i:stack){
                        list.add(new Integer(i));
                    }
                    list.add(new Integer(root.val));
                    all.add(list);
            }else{
                stack.push(new Integer(root.val));
                FindPath(root.left,target-root.val,stack,all);
                FindPath(root.right, target-root.val, stack, all);
                stack.pop();
            }
         }

#### 使二叉树变为其镜像 ####

类似先序遍历的方法

public void mirror(TreeNode node){
            if(node==null)
                return;
            TreeNode n=node.left;
            node.left=node.right;
            node.right=n;
            mirror(node.left);
            mirror(node.right);
        }

#### 判断二叉树是否对称 ####

左节点的右子树和右节点的左子树相同 使用递归

boolean isSymmetrical(TreeNode pRoot){
            if(pRoot==null)
                return true;
            return comRoot(pRoot.left,pRoot.right);
        }
        
        boolean comRoot(TreeNode left,TreeNode right){
            if(left==null)
                return right==null;
            if(right==null)
                return false;
            if(left.val!=right.val)
                return false;
            return comRoot(left.right, right.left)&&comRoot(left.left, right.right);
        }

#### 树的子结构 ####

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）  
第一步：查找与根节点值一样的节点，实际上是树的遍历。可以递归实现。  
第二步：判断树A中以R为根节点的子树是不是和树B具有相同的结构。如果值不同，肯定不同。如果相同，再递归判断各自左右节点。终止条件时到了树A或树B根节点。

public class Solution {
            
         public boolean HasSubtree(TreeNode root1,TreeNode root2) {
               boolean result=false;
               if(root1!=null&&root2!=null){
                   if(root1.val==root2.val){
                       result=DoesTree1HaveTree2(root1,root2);
                   }
                   if(!result)
                       result=HasSubtree(root1.left, root2);
                   if(!result)
                       result=HasSubtree(root1.right, root2);
               }
               return result;
            }
         
         public boolean DoesTree1HaveTree2(TreeNode root1,TreeNode root2){
             if(root1==null&&root2!=null)
                 return false;
             if(root2==null)
                 return true;
             if(root1.val!=root2.val)
                 return false;
             return DoesTree1HaveTree2(root1.left, root2.left)&&DoesTree1HaveTree2(root1.right, root2.right);
         }
    }

#### 多行打印二叉树 ####

public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
            ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();   
            if(pRoot==null)
                return result;
            Queue<TreeNode> layer=new LinkedList<>();
            ArrayList<Integer> list=new ArrayList<Integer>();
           layer.add(pRoot);
           int start=0,end=1;
           while(!layer.isEmpty()){
               TreeNode cur=layer.remove();
               list.add(cur.val);
               start++;
               if(cur.left!=null)
                   layer.add(cur.left);
               if(cur.right!=null)
                   layer.add(cur.right);
               if(start==end){
                   end=layer.size();
                   start=0;
                   result.add(list);
                   list=new ArrayList<>();
               }
           }
           return result;
        }

#### 之字形打印二叉树 ####

利用栈后进先出的特性，两个栈一个存奇数层节点，一个存偶数层节点

/*
         * 请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，
         * 第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
         */
        //{8,6,10,5,7,9,11}
        public static ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
            ArrayList<ArrayList<Integer>> all=new ArrayList<ArrayList<Integer>>();  
            int layer=1;
            Stack<TreeNode> s1=new Stack<TreeNode>();
            Stack<TreeNode> s2=new Stack<TreeNode>();
            s1.push(pRoot);
            while(!s1.empty()||!s2.empty()){
                if(layer%2!=0){
                    ArrayList<Integer> temp=new ArrayList<Integer>();
                    while(!s1.empty()){
                        TreeNode node=s1.pop();
                        if(node!=null){
                            temp.add(node.val);
                            System.out.print(node.val + " ");
                            s2.push(node.left);
                            s2.push(node.right);
                        }
                    }
                    if(!temp.isEmpty()){
                        all.add(temp);
                        layer++;
                        System.out.println();
                    }
                }else{
                    ArrayList<Integer> temp=new ArrayList<Integer>();
                    while(!s2.empty()){
                        TreeNode node=s2.pop();
                        if(node!=null){
                            temp.add(node.val);
                            System.out.print(node.val + " ");
                            s1.push(node.right);
                            s1.push(node.left);
                        }
                    }
                    if(!temp.isEmpty()){
                        all.add(temp);
                        layer++;
                        System.out.println();
                    }
                }
                
            }
            return all;
        }

#### 重构二叉树 ####

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8\}和中序遍历序列\{4,7,2,1,5,3,8,6\}，则重建二叉树并返回。

public TreeNode reConstructBinaryTree(int[] pre,int[] in){
            if(pre.length==0||in.length==0)
                return null;
            TreeNode node=new TreeNode(pre[0]);
            for(int i=0;i<in.length;i++){
                if(pre[0]==in[i]){
                    node.left=reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1),Arrays.copyOfRange(in, 0, i));
                    node.right=reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(in, i+1, in.length));
                }
            }
            return node;
        }

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

给定一颗二叉搜索树，请找出其中的第k大的结点。例如， 5 / \\ 3 7 /\\ /\\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。

public class Solution {
        int index=0;
        TreeNode KthNode(TreeNode root, int k)
        {
            if(root!=null){
                TreeNode node=KthNode(root.left,k);
                if(node!=null)
                    return node;
                index++;
                if(index==k)
                    return root;
                node=KthNode(root.right,k);
                if(node!=null)
                    return node;
            }
            return null;
        }  
    }