数据结构二叉树相关面试题 Java版 LeetCode题 ------- 二叉树

转x33g5p2x  于2022-03-10 转载在 Java  
字(17.0k)|赞(0)|评价(0)|浏览(257)

基础面试题

第一题: 二叉树的前序遍历。

LeetCode144: 二叉树的前序遍历
描述:
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

(递归解法)

class Solution {
	public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) return list;
		//访问根节点,将根节点加入list中
        list.add(root.val);
        //递归遍历左子树,把左子树的遍历结果加入到List中
        list.addAll(preorderTraversal(root.left));        
        //递归遍历右子树,把右子树的遍历结果加入到List中
        list.addAll(preorderTraversal(root.right));
        return list;
    }
}

(迭代解法)

思路:

  1. 迭代就是按照遍历的思路一步一步走.
  2. 用栈(Stack)来存入节点,按照: 根 -> 左 -> 右 的顺序存,
  3. 先入栈根节点,将根节点的值,插入到list中,再去入栈左节点
    ①如果左节点不为空,循环去入栈左节点,每次入栈时,将节点的值插入到list中,直到左节点为空,进入②操作
    ②如果左节点为空,就出栈获取栈顶元素的节点,然后访问该节点的右节点.循环 3.操作

代码实现:

public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        // 节点不为空 或者 栈不为空的时候进入循环
        while(cur != null || !stack.empty()){
        	// 节点不为空的时候入栈 同时插入list中然后让节点指向左节点.
            while(cur != null){
                stack.push(cur);
                list.add(cur.val);
                cur = cur.left;
            }
            //节点为空表示,没有左节点了,此时要弹出栈顶元素
            TreeNode top = stack.pop();
            //指向该节点的右节点,然后继续进行循环
            cur = top.right;
        }
        return list;
    }

第二题: 二叉树的中序遍历。

LeetCode 94: 二叉树的中序遍历
描述:
给定一个二叉树的根节点 root ，返回它的 中序 遍历。

(递归解法)

class Solution {
   public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) return list;

        //递归遍历左子树,把左子树的遍历结果加入到List中
        list.addAll(inorderTraversal(root.left));        
		//访问根节点,将根节点加入list中
        list.add(root.val);
        //递归遍历右子树,把右子树的遍历结果加入到List中
        list.addAll(inorderTraversal(root.right));
        return list;
    }
}

(迭代解法)

思路:

  1. 中序的迭代 和 前序的迭代差不多,只不过是插入list的时机不一样
  2. 这里的list插入是出栈的时候插入,因为栈顶肯定是先左子树,再父节点,然后右子树的. 相当于 左 -> 根 -> 右
public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while (cur != null || !stack.empty()) {
            while (cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            list.add(top.val);//出栈的时候 插入list中
            cur = top.right;
        }
        return list;
    }

第三题: 二叉树的后序遍历。

LeetCode 145: 二叉树的后序遍历
描述:
给定一个二叉树，返回它的 后序 遍历。

(递归解法)

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) return list;

        //递归遍历左子树,把左子树的遍历结果加入到List中
        list.addAll(postorderTraversal(root.left));        
        //递归遍历右子树,把右子树的遍历结果加入到List中
        list.addAll(postorderTraversal(root.right));
        //访问根节点,将根节点加入list中
        list.add(root.val);
        return list;
    }
}

(迭代解法)

思路:

  1. 相对于 前序 和 中序的 迭代,后序的迭代方法要更加难一点.
  2. 在循环将左子树入栈的时候,循环结束,不能直接出栈,要判断该左子树右节点是否还有节点,如果有节点要先将右节点插入到list中,如果没有右节点,表示该节点就是最左边的节点,直接出栈.
public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) return list;
        TreeNode cur = root;
        TreeNode pre = null;
        Stack<TreeNode> stack = new Stack<>();

        while(cur != null || !stack.empty()){
            while (cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            //先判断栈顶元素是否还有右子树(因为是左->右->根,没有左节点了,还需要判断右节点.)
            cur = stack.peek();
            //如果没有右子树,或者右子树已经插入了,就继续出栈.
            if(cur.right == null || cur.right == pre){
            	//该节点没有右子树了,出栈 插入到list中即可.
                TreeNode topCur = stack.pop();
                list.add(topCur.val);
               
                pre = cur; //pre指向被插入的节点.用来判断是否插入过了
                cur = null;
            }else {
                cur = cur.right;
            }
        }
        return list;
    }

第四题: 相同的树

LeetCode 100: 相同的树
描述:
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

解题思路:

1. 如果两个二叉树都为空，则两个二叉树相同。
2. 如果两个二叉树中有且只有一个为空，则两个二叉树一定不相同。
3. 如果两个二叉树都不为空，那么首先判断它们的根节点的值是否相同， 若不相同，则两个二叉树一定不同， 若相同，再分别判断两个二叉树的左子树是否相同以及右子树是否相同。
4. 根据这3个条件,遍历两个二叉树的左子树和右子树是否相等.

代码实现:

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
    	//如果p q 节点同时为空 则相等
        if(p == null && q == null) return true;
        //1.如果p为空,q不为空 不相等
        //2.如果p不为空,q为空 不相等
        //3.p q都不为空,p的值 和 q的值 不相等
        if(p == null || q== null || p.val != q.val) return false;
        //递归左子树是否相等 和 右子树是否相等
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
}

第五题: 另一棵树的子树

LeetCode 572: 另一棵树的子树
描述:
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

解题思路:

1. 情况一 : 两个树 root 和 subRoot 是相同的
2. 情况二 : 左子树 root.left 和 subRoot 是相同的
3. 情况三 : 右子树 root.left 和 subRoot 是相同的
4. 不符合三种情况就是 subRoot 不是 root 的子树
5. 递归 为空 和 不符合情况 都是 false;比较相同用第四题的代码.

代码实现:

/**
	* 判断是否是相同的树
	**/
    public boolean isSameTree(TreeNode p,TreeNode q){
        if(p == null && q == null) return true;
        if(p == null || q== null || p.val != q.val) return false;
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
    
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    	// 递归遍历之后 为空 就是 flase;
        if(root == null || subRoot == null) return false;
        // 判断两个树是否相同
        if(isSameTree(root,subRoot)) return true;
        // 判断subRoot 是否是 root 的左子树
        if(isSubtree(root.left,subRoot)) return true;
        // 判断subRoot 是否是 root 的右子树
        if(isSubtree(root.right,subRoot)) return true;
        // 遍历结束还不相同 所以返回false;
        return false;
    }

第六题: 二叉树最大的深度

LeetCode 104: 二叉树最大的深度
描述:
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

返回它的最大深度 3 。

解题思路:

1. 求出左子树的高度 leftHeight 和 右子树的高度 rightHeight.
2. 求出左子树和右子树的最大值
3. 求出最大值还需要＋1

代码实现:

public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        int leftHeight = maxDepth(root.left);// 左子树的深度
        int rightHeight = maxDepth(root.right);// 右子树的深度
		//求出最大值然后+1 就是树的最大深度
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }

第七题: 判断一颗二叉树是否是平衡二叉树。

LeetCode 110: 平衡二叉树
描述:
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

方法一：自顶向下的递归—时间复杂度O(N^2)

1. 利用第六题的代码 可以求出任意节点的深度.
2. 自顶向下递归,每次判断当前节点的左右子树的高度差是否<=1,如果始终符合就是平衡二叉树,否则就是非平衡二叉树.
3. 然后递归的遍历这个节点的左节点 和 右节点,判断他们的左子树和右子树的差是否符合要求.

代码实现:
/**
	* 求节点深度
	**/
	public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }
   
    public boolean isBalanced(TreeNode root) {
    	//节点为空的时候也符合条件 所有直接return true
        if(root == null){
            return true;
        }
        //求出左子树的深度 和 右子树的深度
        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);
  		
  		//Math.abs()求出左右子树差的绝对值 如果<2就是true否则就是false
  		//isBalanced分别递归遍历节点的左节点和右节点的左右子树 是否符合题意      
        return Math.abs(leftHeight - rightHeight) < 2 && isBalanced(root.left) && isBalanced(root.right);
    }

方法二: 自底向上的递归—时间复杂度O(N)

1. 对于当前遍历到的节点,先判断他的左右子树 是否平衡,再判断以当前节点为根的树是否平衡,
2. 如果子树是平衡的,返回子树的高度,
3. 如果子树不是平衡的,那么整个树都不会是平衡的,返回-1;

代码实现:
public int maxDepth(TreeNode root){
    	//如果节点为空,就返回0
        if(root == null) return 0;
        //递归求左子树的高度
        int leftHeight = maxDepth(root.left);
        //递归求右子树的高度
        int rightHeight = maxDepth(root.right);
        //判断差值符合条件 且 左子树高度和右子树高度都>=0 则返回节点高度
        if(leftHeight >= 0 && rightHeight >= 0 && Math.abs(leftHeight-rightHeight) <=1){
            return Math.max(leftHeight,rightHeight) + 1;
        }else {
        	//如果不是平衡二叉树就返回-1
            return -1;
        }
    }
    public boolean isBalanced(TreeNode root){
    	//如果为负数就是false
        return maxDepth(root) >= 0;
    }

第八题: 对称二叉树

LeetCode 101: 对称二叉树
描述:
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

解题思路:

1. 递归解题,思路: ①.如果根节点为空,那么就对称. ②判断根节点的左右子树是否是对称
2. 判断是否对称的方法,如图可以看出,左子树的左孩子和右子树的右孩子相等,左子树的右孩子 和 右子树的左孩子相等.那么就是对称.
3. 由此可以利用第四题,相同的树的代码来实现.
4. 第四题是判断两个节点的左子树是否相同,此题只需要修改判断左子树的左节点,和右子树的右节点是否相同即可.

代码实现:

class Solution {
    public boolean isSameTree(TreeNode p,TreeNode q){
    	//如果两个节点同时为空,就是对称
        if(p == null && q == null) return true;
        //如果两个节点有一个为空,另一个不为空,则不对称
        //如果两个节点的值不相等就不对称.
        if(p == null || q == null || p.val != q.val) return false;
      	// 判断左子树的左孩子和右子树的右孩子是否相等.
      	// 判断左子树的有孩子和右子树的左孩子是否相等.
        return isSameTree(p.left,q.right) && isSameTree(p.right,q.left);
    }
    public boolean isSymmetric(TreeNode root) {
        return isSameTree(root.left,root.right);
    }
}

第九题: 二叉树的镜像

NC72 : 二叉树的镜像
描述:
操作给定的二叉树，将其变换为源二叉树的镜像。
数据范围：二叉树的节点数 0≤n≤1000 ， 二叉树每个节点的值0≤val≤1000
要求： 空间复杂度O(n) 。本题也有原地操作，即空间复杂度O(1) 的解法，时间复杂度O(n)
比如：
源二叉树

镜像二叉树

解题思路:

1. 求镜像二叉树,让左右子树交换,再让左右子树的左右子树交换,递归这个思路就行,
2. 情况一 节点为空,直接返回空节点
3. 情况二 只有该节点,没有子节点,直接返回该节点.
4. 不符合这两种情况就交换节点,然后进入递归.

代码实现:

public TreeNode Mirror (TreeNode pRoot) {
		// 节点为空 直接返回
        if(pRoot == null) return pRoot;
        // 当前节点没有左右节点,直接返回该节点
        if(pRoot.left == null && pRoot.right == null) return pRoot;
        // 交换左右节点
        TreeNode tmp = pRoot.left;
        pRoot.left = pRoot.right;
        pRoot.right = tmp;
        // 处理左子树
        Mirror(pRoot.left);
        // 处理右子树
        Mirror(pRoot.right);
        return pRoot;
    }

进阶面试题

第一题: 二叉树的构建及遍历。

牛客: 二叉树遍历
描述:
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串:ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

解题思路:

  1. 整体看来 要输入一个字符串, 然后要将字符串 变成 二叉树, 然后输出中序遍历
  2. 输入字符串用Scanner 中序遍历(用递归解法).
  3. 遍历字符串,根据下标把他们串起来.
  4. 该树的图形如图:

代码实现:

import java.util.*;
class TreeNode {
    public char val;
    public TreeNode left;
    public TreeNode right;
    
    public TreeNode(char val){
        this.val = val;
    }
}

public class Main{
    public static int i = 0;//在外部定义静态的i以防递归的时候改变了i的值
    public static TreeNode createTree(String str){
        if(str == null) return null;
        TreeNode root = null;
        // 遍历字符串 如果 字符等于'#'就直接i++后return;
        //    如果 字符不等于'#' 就定义这个节点,然后链接左右结点,进入递归
        if(str.charAt(i) != '#'){
            root = new TreeNode(str.charAt(i));
            i++;
            root.left = createTree(str);
            root.right = createTree(str);
        }else{
            i++;
        }
        return root;
    }
    //中序遍历
    public static void inorder(TreeNode root) {
        if(root == null) {
            return;
        }
        inorder(root.left);
        System.out.print(root.val+" ");
        inorder(root.right);
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        
        TreeNode root = createTree(str);
        
        inorder(root);
    }
}

第二题: 二叉树的分层遍历 。

LeetCode 102 : 层序遍历
描述:
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

解题思路:

1. 用队列实现层序遍历(先进先出)
2. 先根元素入队,当队列不为空的时候循环求出队列长度
3. 循环根据队列的长度,出队首元素,然后插入到list当中,然后将他的不为空的左右节点入队,重复这个操作直到队的长度为0;

代码实现:

public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) return ret;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);//根节点先入队
        //队不为空进入循环
        while (!queue.isEmpty()){
            List<Integer> list = new ArrayList<>();
            //求出队的长度
            int size = queue.size();
            //size不为空进入循环
            while (size != 0) {
                //出队首元素,然后插入list中
                TreeNode top = queue.poll();
                list.add(top.val);
                //看左右节点是否为空,不为空的节点入队
                if (top.left != null)
                    queue.offer(top.left);
                if (top.right != null)
                    queue.offer(top.right);
                size--;
            }
            ret.add(list);//添加这一层的元素到ret中
        }
        return ret;
    }

第三题: 二叉树的最近公共祖先

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

解题思路:

1. 分情况讨论
①p 和 q 有一个为根节点的时候,公共祖先就是根节点.
②p 和 q 不在同一颗子树下, 那么 他们的父亲 就是 公共祖先
③p 和 q在同一颗子树下 ④root 为 null 直接返回 null
2. 递归左右子树,
①如果左右子树都不为空,那么root就是他们的公共祖先
②如果左子树为空 右子树不为空,那么右树找到的节点就是公共祖先
③如果右子树为空 左子树不为空,那么左树找到的节点就是公共祖先

画图解析:

代码实现:

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    	//节点为空,直接返回
        if(root == null) return null;
        //p 和 q 有一个为根root的时候,root就是公共祖先
        if(p == root || q == root) return root;
        //分别找左右子树的符合的节点
        TreeNode leftNode = lowestCommonAncestor(root.left,p,q);
        TreeNode rightNode = lowestCommonAncestor(root.right,p,q);
        //如果左右子树的找到的节点都不为空,表示根节点root就是他们的公共祖先
        if(leftNode != null && rightNode != null){
            return root;
        }
        //走到这里,s
        if(leftNode == null){
            return rightNode;
        }
        if(rightNode == null){
            return leftNode;
       }
       return null;
    }

第四题: 二叉树搜索树转换成排序双向链表。

剑指 Offer 36 : 二叉搜索树与双向链表
描述:
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

为了让您更好地理解问题，以下面的二叉搜索树为例：

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

解题思路:

  1. 二叉搜索树的中序遍历为 递增序列 。
  2. 根据这个条件,利用中序遍历,从小到大访问到各个节点.
  3. 然后利用 root.left 和 root.right 分别当初双向链表 的 prev 和 next .
  4. 根据题目的意思还需要将,首尾相连,变成循环的双向链表
  5. 引用一个pre 用于记录双向链表中位于root左侧的节点，即上一次迭代中的root,
    ①当pre==null时，root左侧没有节点,即此时root为双向链表中的头节点,可以引用一个head记录该节点
    ②当pre!=null时，root左侧存在节点pre，需要进行pre.right=cur的操作。
    ③root迭代返回时,root指向的是下一个节点,pre是上一节点,让root.left指向pre即可,当第一次指向时,pre正好为null.
  6. 当迭代结束,pre的位置就是尾节点的位置,head的位置就是头节点的位置,此时链接两个节点,就是循环双向链表了.

画图解析:

代码实现:

// 在外部 以免内部递归的时候 改变了 prev 和head的值
    public Node prev = null;
    public Node head = null;

    public void inoderTree(Node root){
        if(root == null) return ;// 递归终止条件 节点为空

        inoderTree(root.left);
        //节点的左边链接prev
        root.left = prev;  
        // 当prev不为空的时候,将prev的右边和root连接起来   
        if(prev != null) {
            prev.right = root;
        }else{
        //当prev为空,root就是最左节点,也是循环列表的头节点
            head = root;
        }
        //始终让prev指向root的前一个节点
        prev = root;
        inoderTree(root.right);
        
    }

    public Node treeToDoublyList(Node root) {
        if(root == null) return null;

        inoderTree(root);
        //链接两个节点的头尾 变成循环列表
        head.left = prev;
        prev.right = head;

        return head;
    }

第五题: 根据一棵树的前序遍历与中序遍历构造二叉树。

LeetCode 105: 从前序与中序遍历序列构造二叉树
**描述: **
给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。

解题思路:

  1. 首先我们可以先观察一下如下题目:
    PreOrder : G D A F E M H Z
    InOrder : A D E F G H M Z 构造二叉树:

  1. 根据图介绍,可以发现,我们可以
    ① 先 遍历 前序的结果.每次拿到的就是一个根节点
    ②根据每次拿的节点 在 中序遍历中去找到该节点, 该节点的左边就是左子树,右边就是右子树.

代码实现:

private int index ; //index就是遍历前序数组的下标
	
	// 根据[left,right]的范围,构造一个树
    public TreeNode buildTreeChild(int[] preorder,int[] inorder,int left ,int right){
        if(left > right) return null;//left>right表示这次中序数组结束
        if(index >= preorder.length) return null;//表示遍历结束

		//root表示当前根据index下标下的根节点
        TreeNode root = new TreeNode(preorder[index]);
        index++;

		//pos就是中序数组中和root相等的节点
        int pos = find(inorder,left,right,root.val);
        // post的左边就是左子树
        root.left = buildTreeChild(preorder,inorder,left,pos - 1);
        // post的右边就是右子树
        root.right = buildTreeChild(preorder,inorder,pos + 1,right);
		
		//结束返回该根节点
        return root;
    }
	//找到中序数组中 和 前序数组index下标下,相同的节点
    public int find(int[] inorder,int left,int right,int key){
        for (int i = left; i <= right; i++) {
            if(inorder[i] == key){
                return i;
            }
        }
        return -1;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder,inorder,0,inorder.length - 1);
    }

第六题: 根据一棵树的中序遍历与后序遍历构造二叉树。

LeetCode 106: 从中序与后序遍历序列构造二叉树
描述:
根据一棵树的中序遍历与后序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

解题思路

  1. 这里我们也看一个题
    中序遍历: A D E F G H M Z``后序遍历: A E F D H Z M G 构造二叉树:

  1. 根据图的操作可以发现,这题的解答过程,和第五题的,差不多,只不过是把后序遍历的镜像求出来,然后遍历镜像的数组.
  2. 还有一个不同点就是,此时遍历的节点,在中序数组中找到这个节点,这此左右顺序改变了.先右边再左边.

代码实现:

private int index ; //index就是遍历镜像数组的下标
	//根据[left,right]的范围,构造一个树
    public TreeNode buildTreeChild(int[] preorder,int[] inorder,int left ,int right){
        if(left > right) return null;//表示这次递归的左右没有节点了
        if(index >= preorder.length) return null;//遍历结束了

		//root表示index下标下镜像数组的根节点
        TreeNode root = new TreeNode(preorder[index]);
        index++;
		//pos就是中序数组中和root相等的节点
        int pos = find(inorder,left,right,root.val);
        //先走post的右边
        root.right = buildTreeChild(preorder,inorder,pos + 1,right);
        //后走post的左边
        root.left = buildTreeChild(preorder,inorder,left,pos - 1);
        return root;
    }
    public int find(int[] inorder,int left,int right,int key){
        for (int i = left; i <= right; i++) {
            if(inorder[i] == key){
                return i;
            }
        }
        return -1;
    }
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int[] makePreOrder = new int[postorder.length];
        //镜像数组.
        int j = 0;
        for (int i = postorder.length - 1; i >= 0; i--) {
            makePreOrder[j++] = postorder[i];
        }
        return buildTreeChild(makePreOrder,inorder,0,inorder.length-1);
    }

第七题: 根据二叉树创建字符串

LeetCode 606: 根据二叉树创建字符串
描述:
你需要采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串。
空节点则用一对空括号 “()” 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

解题思路:

  1. 分析括号省略的注意事项:
    ① 如果一个树的左右子树都为空,就不需要把左右子树用"()"表示
    ② 如果一个树的左子树为空,右子树非空,需要把左子树用"()"占位.不能省略括号
    ③如果一个树的左子树非空,右子树为空,右子树的括号"()"需要省略

代码实现:

private StringBuffer sb = new StringBuffer();
    public String tree2str(TreeNode root) {
        if(root == null){
            return "";//返回空字符,而不是null
        }
        helper(root);
        //因为递归后,最外层还有一层括号,所以要省略最外层的括号
        sb.deleteCharAt(0);
        sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }
    
    public void helper(TreeNode root){
        if(root == null) return;//节点为空直接返回
        
        sb.append("(");
        sb.append(root.val);
        helper(root.left);
        //如果左子树为空,右子树不为空,要加上()
        if(root.left == null && root.right != null){
            sb.append("()");
        }
        helper(root.right);
        sb.append(")");
    }

其他LeetCode 二叉树的题

第一题: 二叉树的锯齿形层序遍历

LeetCode 103 : 二叉树的锯齿形层序遍历
描述:
给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如：
给定二叉树 [3,9,20,null,null,15,7],

解题思路:

1. 这题相对于 层序遍历 那题,就是把偶数层 倒着插入到了list中.
2. 这里我们可以定义一个boolean类型的变量,用if语句,如果第一次进入,就是ture,第二次就是false,第一次进入就尾插,第二次进入就头插.

代码实现:

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) return ret;//root为空直接返回
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean flg = false;//用flg来判断是奇数次还是偶数次
        while(!queue.isEmpty()){
            List<Integer> list = new ArrayList<>();
            int size = queue.size();
            while(size != 0){
                TreeNode top = queue.poll();
                list.add(top.val);
                if(top.left != null){
                    queue.offer(top.left);
                }
                if(top.right != null){
                    queue.offer(top.right);
                }
                size--;
            }
            //奇数次进入if,偶数次进入else
            if(!flg) {
                ret.add(list);
                flg = true;
            }else{
                List<Integer> list1 = new ArrayList<>();
                for (int i = 0; i < list.size() ; i++) {
                    list1.add(0,list.get(i));
                }
                //list1是头插法
                ret.add(list1);
                flg = false;
            }
        }
        return ret;
    }

第二题: 二叉树的最小深度

LeetCode 111 : 二叉树的最小深度
描述:
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。

解题思路:

1. 跟求最大深度解法差不多.
2. 分情况讨论
① 如果root为空的时候,直接返回.
② 如果左子树的深度为0 或者 右子树深度为0时,返回较大的深度,因为深度为0就代表没有那一边.
③ 如果左子树 和 右子树 都不等于 0 ,这时返回一个较小的值
3. 返回的值都要 +1

代码实现:

public int minDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        int leftHeiht = minDepth(root.left);
        int rightHeight = minDepth(root.right);
        //都不为空的时候,求出左右子树中 最小深度 + 1
        if(leftHeiht != 0 && rightHeight != 0){
            return leftHeiht > rightHeight ? rightHeight + 1 : leftHeiht + 1;
        }
        //如果左右子树有一个为空,就代表没有该子树,所以求出另一个子树的深度+!
        if(leftHeiht ==0 || rightHeight == 0){
            return leftHeiht < rightHeight ? rightHeight + 1 : leftHeiht + 1;
        }
        return 0;
    }

第三题: 二叉树的层序遍历 Ⅱ

LeetCode 107 : 二叉树的层序遍历Ⅱ
描述:
给定一个二叉树，返回其节点值自底向上的层序遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

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

解题思路:

1. 这题也是根据 层序遍历 变形而来的.
2. 这题是从最下层先打印出来.可以直接在插入list时,使用头插法,先插入的在后层.

代码实现:

public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) return ret;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            List<Integer> list = new ArrayList<>();
            int size = queue.size();
            while (size != 0) {
                TreeNode top = queue.poll();
                list.add(top.val);
                if (top.left != null)
                    queue.offer(top.left);
                if (top.right != null)
                    queue.offer(top.right);
                size--;
            }
            ret.add(0,list);//直接头插
        }
        return ret;
    }

第四题: 二叉树的右视图

LeetCode 199: 二叉树的右视图
描述:
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值

解题思路:

  1. 跟层序遍历差不多.层序遍历每次是插入一层元素. 这里只需要插入每一层最后一个元素即可.
  2. 插入技巧 size == 0的时候插入.

代码实现:

public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root == null) return ret;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            while(size != 0){
                TreeNode top = queue.poll();
                if(top.left != null) queue.add(top.left);
                if(top.right != null) queue.add(top.right);
                size--;
                //层序遍历中 只添加每一层的最后一个节点的值即可.
                if(size == 0){
                    ret.add(top.val);
                }
            }
        }
        return ret;
    }

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/wwzzzzzzzzzzzzz/article/details/121870443

内容来源于网络，如有侵权，请联系作者删除！

Java数据结构leetcode二叉树

相关文章

    查看更多
    微信公众号

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多

    目录

    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com