标签: 二叉树

LeetCode刷题【114】二叉树展开为链表

给你二叉树的根结点 root ,请你将它展开为一个单链表:

  • 展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null
  • 展开后的单链表应该与二叉树 先序遍历 顺序相同。

 

示例 1:

输入:root = [1,2,5,3,4,null,6]
输出:[1,null,2,null,3,null,4,null,5,null,6]

示例 2:

输入:root = []
输出:[]

示例 3:

输入:root = [0]
输出:[0]

 

提示:

  • 树中结点数在范围 [0, 2000]
  • -100 <= Node.val <= 100

 

进阶:你可以使用原地算法(O(1) 额外空间)展开这棵树吗?

Related Topics
  • 深度优先搜索
  • 链表
  • 二叉树

  • 👍 1219
  • 👎 0
  • 前序遍历,原地递归修改
    按照题意为前序遍历的结果,声明一个TreeNode pre记录前一个访问的节点

    这样直接进行前序遍历,把当前节点挂载到pre节点的right上,记得要清除left节点

    遍历当前节点的时候leftright节点的值记得先存下来,会在递归的时候被修改掉

    代码

    class Solution {
        /*
            1
        2       5
      3   4   n   6
    
            1
          n   2
            n   3
              n   4
                n   5
                  n   6
    
         */
        TreeNode pre;
        public void flatten(TreeNode root) {
            dfs(root);
        }
    
    
        public void dfs(TreeNode node){
            if (null == node){
                return;
            }
            if (pre!=null){
                pre.right = node;
            }
            pre = node;
            TreeNode left = node.left;
            TreeNode right = node.right;
            node.left = null;
            dfs(left);
            dfs(right);
        }
    }

    LeetCode刷题【637】二叉树的层平均值

    给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

     

    示例 1:

    输入:root = [3,9,20,null,null,15,7]
    输出:[3.00000,14.50000,11.00000]
    解释:第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
    因此返回 [3, 14.5, 11] 。
    

    示例 2:

    输入:root = [3,9,20,15,7]
    输出:[3.00000,14.50000,11.00000]
    

     

    提示:

    • 树中节点数量在 [1, 104] 范围内
    • -231 <= Node.val <= 231 - 1
    Related Topics
    • 深度优先搜索
    • 广度优先搜索
    • 二叉树

  • 👍 354
  • 👎 0
  • bfs

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

    LeetCode刷题【剑指 Offer 33】二叉搜索树的后序遍历序列

    输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。

     

    参考以下这颗二叉搜索树:

         5
        / \
       2   6
      / \
     1   3

    示例 1:

    输入: [1,6,3,2,5]
    输出: false

    示例 2:

    输入: [1,3,2,6,5]
    输出: true

     

    提示:

    1. 数组长度 <= 1000
    Related Topics
    • 二叉搜索树
    • 递归
    • 二叉树
    • 单调栈

  • 👍 541
  • 👎 0
  • 分段验证

    解题思路

    分段验证

    代码

    class Solution {
        public boolean verifyPostorder(int[] postorder) {
            return validate(postorder,0,postorder.length-1);
        }
    
    
        private boolean validate(int[] postorder, int left ,int right){
            //如果左指针大于等于右指针了,说明当前节点以及没有子节点了,自然是符合条件的】
            if (left>=right || left < 0 || right < 0) return true;
            //找到这段数组对应的根节点,根据后序遍历的特性,即为这段数组的最后一位
            int rootNum = postorder[right];
            //初始赋值
            int leftEnd = -1;
            int rightStart = -1;
            //开始遍历
            for (int i = left; i < right; i++) {
                if (postorder[i] < rootNum){
                    //如果这个值小于根节点的值,说明这个节点应该是在左子树中
                    leftEnd = i;
                }
                if (postorder[i] > rootNum && rightStart == -1){
                    //如果这个值大于根节点的值,说明这个节点应该是右子树上的
                    //且rightStart == -1 表示是第一次碰到的
                    rightStart = i;
                }
            }
            //此时如果符合条件的话,应该是 leftEnd 在 rightStart 的左边一位
            //或者  没有左子树:leftEnd == -1 且rightStart == left
            //或者  没有右子树:rightStart == -1 且leftEnd == right-1
            boolean validateResult = (leftEnd>-1 &&  rightStart> -1 && leftEnd+1== rightStart)
                    || ( leftEnd == -1 && rightStart == left )
                    || ( rightStart == -1 && leftEnd == right-1);
            //自身验证完了,还要对分割好了的子序列的有效性判断
            if (validateResult){
                return validate( postorder, left, leftEnd ) && validate( postorder, rightStart, right-1 );
            }
            return false;
        }
    }

    LeetCode刷题【剑指 Offer 07】重建二叉树

    输入某二叉树的前序遍历和中序遍历的结果,请构建该二叉树并返回其根节点。

    假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

    示例 1:

    Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
    Output: [3,9,20,null,null,15,7]
    

    示例 2:

    Input: preorder = [-1], inorder = [-1]
    Output: [-1]
    

    限制:

    0 <= 节点个数 <= 5000

    注意:本题与主站 105 题重复:https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/ Related Topics

    • 数组
    • 哈希表
    • 分治
    • 二叉树

    👍 830👎 0

    学二叉树入门必做题

    学二叉树入门必做

    关键信息

    1. 前序遍历的第一个值为根节点
    2. 到中序遍历中找到根节点所在位置,前面的部分为左子节点内容,后面的部分为右子节点内容
    3. 得到的左右子节点的长度,重新回到前序遍历的结果中,根节点后面对应左子节点长度的部分为左子树的前序遍历,后面一部分为右子树的前序遍历
    4. 拿到了步骤3和2的左子树的中序和前序遍历结果 重新做步骤1,右子树部分也同样走步骤1

    前中后序遍历

    左右两个子节点的顺序不变都是先左子节点,后右子节点,区别就在于根节点是先遍历,还是中间,还是最后

    这分别就是前中后序遍历

    相关特性

    现有如图这个一对前序遍历和中序遍历结果

    根据相关特效,前序遍历的第一个就是根节点,所以我们知道了,根节点为3

    又中序遍历中左侧只有一个,所以左子树只有一个节点9,右子树部分暂时不知道只知道剩下部分为右侧的前序和中序遍历结果,二叉树如下

    再接下来,我们把右子树部分的按照同样的逻辑处理

    我们知道了右子树的根节点为20,20的左子树只有一个节点15,右子树只有一个节点7

    这样我们就重新构建完成了整棵二叉树

    代码

    class Solution {
        int[] preorder;
        int[] inorder;
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            this.preorder = preorder;
            this.inorder = inorder;
            int len = preorder.length-1;
            return buildTree(0,len,0,len);
        }
    
        public TreeNode buildTree( int preL, int preR, int inL, int inR){
            if (preL > preR){
                return null;
            }
            TreeNode node = new TreeNode(preorder[preL]);
            int len = 0;
            for (int i = inL; i <= inR; i++) {
                if (inorder[i] == preorder[preL]){
                    len = i - inL;
                }
            }
            node.left = buildTree(preL+1,preL+len,inL,inL+len-1);
            node.right = buildTree(preL+len+1,preR,inL+len+1,inR);
            return node;
        }
    }

    LeetCode刷题【剑指 Offer 68 – I】二叉搜索树的最近公共祖先

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

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

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

     

    示例 1:

    输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
    输出: 6 
    解释: 节点 2 和节点 8 的最近公共祖先是 6。
    

    示例 2:

    输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
    输出: 2
    解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

     

    说明:

    • 所有节点的值都是唯一的。
    • p、q 为不同节点且均存在于给定的二叉搜索树中。

    注意:本题与主站 235 题相同:https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

    Related Topics
    • 深度优先搜索
    • 二叉搜索树
    • 二叉树

  • 👍 239
  • 👎 0
  • 二叉搜索树特性

    1. 递归

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

    2. 指针

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

    比较简单,不做过多分析了

    LeetCode刷题【剑指 Offer 55 – II】平衡二叉树

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

     

    示例 1:

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

        3
       / \
      9  20
        /  \
       15   7

    返回 true

    示例 2:

    给定二叉树 [1,2,2,3,3,null,null,4,4]

           1
          / \
         2   2
        / \
       3   3
      / \
     4   4
    

    返回 false

     

    限制:

    • 0 <= 树的结点个数 <= 10000

    注意:本题与主站 110 题相同:https://leetcode-cn.com/problems/balanced-binary-tree/

     

    Related Topics
    • 深度优先搜索
    • 二叉树

  • 👍 288
  • 👎 0
  • DFS深搜模板套用

    解题思路

    1. 借助深搜模板,计算每层对应高度
    2. 判断每个节点的左右子节点高度相差是否小于2
    3. 如果不小于2则不是平衡二叉树

    代码

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
    
        boolean isBalanced = true;
        public boolean isBalanced(TreeNode root) {
            dfs(root,0);
            return isBalanced;
        }
    
        public int dfs(TreeNode node, int dep){
            if (!isBalanced || null == node){
                return dep;
            }
            dep++;
            int leftDep = dfs(node.left,dep);
            int rightDep = dfs(node.right,dep);
            if (Math.abs(leftDep-rightDep )< 2){
                return Math.max(leftDep,rightDep);
            }
            isBalanced = false;
            return Math.max(leftDep,rightDep);
        }
    }

    LeetCode刷题【700】二叉搜索树中的搜索

    给定二叉搜索树(BST)的根节点 root 和一个整数值 val

    你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 null 。

     

    示例 1:

    输入:root = [4,2,7,1,3], val = 2
    输出:[2,1,3]
    

    Example 2:

    输入:root = [4,2,7,1,3], val = 5
    输出:[]
    

     

    提示:

    • 数中节点数在 [1, 5000] 范围内
    • 1 <= Node.val <= 107
    • root 是二叉搜索树
    • 1 <= val <= 107
    Related Topics
  • 二叉搜索树
  • 二叉树

  • 👍 293
  • 👎 0
  • 根据二叉搜索树的左小右大的特性【递归&遍历树】

    递归

    class Solution {
        public TreeNode searchBST(TreeNode root, int val) {
            if (root == null){
                return null;
            }
            if (root.val == val){
                return root;
            }
            return root.val > val ? searchBST(root.left, val) : searchBST(root.right, val);
        }
    }

    应该没啥特殊的,二叉搜索树的特性

    左子节点  <   根节点   <  右子节点

    所以照着这个写就行了

    也可以改递归为遍历的写法,毕竟 递归和遍历循环是可以相互转化的

    遍历

    class Solution {
        public TreeNode searchBST(TreeNode root, int val) {
            while (root !=null){
                if (root.val == val) return root;
                root = root.val > val? root.left : root.right;
            }
            return root;
        }
    }