草庐IT

代码随想录 | 二叉树

nnn~ 2023-03-28 原文

226. 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,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;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        Queue<TreeNode> que = new LinkedList<>();
        if (root == null) {
            return root;
        }
        que.add(root);
        while (!que.isEmpty()) {
            int size = que.size();
            while (size > 0) {
                TreeNode node = que.poll();
                TreeNode tmp = new TreeNode();
                if (node.right != null && node.left != null) {
                    //左右孩子都不空，右孩子、左孩子加入队列并交换
                    que.add(node.right);
                    que.add(node.left);
                    tmp = node.right;
                    node.right = node.left;
                    node.left = tmp;
                } else if (node.right==null&&node.left!=null ) {
                    que.add(node.left);
                    node.right=node.left;
                    node.left=null;
                } else if(node.left==null&&node.right!=null){
                    que.add(node.right);
                    node.left=node.right;
                    node.right=null;
                }
                size--;
            }
        }
        return root;
    }
}
  • 下面是递归的做法：
/**
 * 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 TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        //先序遍历
        swapChildren(root);
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    private void swapChildren(TreeNode root) {
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
    }
}



101. 对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

输入：root = [1,2,2,3,4,4,3]
输出：true

ψ(｀∇´)ψ 我的思路

  • 层序遍历每一层二叉树，每一层结点的值放入链表，判断链表（除第一层外）是否对称
/**
 * 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 boolean isSymmetric(TreeNode root) {
        Queue<TreeNode> que = new LinkedList<>();
        que.add(root);
        while (!que.isEmpty()){
            int size = que.size();
            List<Integer> list = new ArrayList<>();
            while (size>0){
                TreeNode node = que.poll();
                list.add(node.val);//加入链表
                if(node.left!=null){que.add(node.left);}
                if(node.right!=null){que.add(node.right);}
                size--;
            }
            //判断list是不是对称列表
            if(list.size()>1){
                Collections.reverse(list.subList(0,list.size()/2));
                if(!list.subList(0,list.size()/2).equals(list.subList(list.size()/2,list.size()))){
                    return false;
                }
            }
        }
        return true;
    }
}

  • 上面的代码并不能判断下面这种情况：

    输入：root = [1,2,2,null,3,null,3]
    输出：false

  • 因为只把不空的结点加入到链表，所以上述情况的链表是这样的：[1][2,2][3,3],我想着把null也加入到链表里。不行(x_x)，那样的话就没办法控制临界条件了。

  • 下面是代码随想录的递归做法：比较根结点的左右子树是否对称

/**
 * 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 boolean isSymmetric(TreeNode root) {
        boolean res = comparable(root.left, root.right);
        return res;

    }
    public static boolean comparable(TreeNode left, TreeNode right){
        if(left==null&&right!=null){return false;}
        else if(right==null&&left!=null){return false;}
        else if(right==null&&left==null){return true;}
        else if(right.val!= left.val){return false;}
        boolean a = comparable(left.left, right.right);//比较外侧结点
        boolean b = comparable(left.right, right.left);//比较内测结点
        boolean res = a && b;
        return  res;
    }
}
  • 感觉递归的做法要好理解很多，再写两道类似的题目练一下递归


100. 相同的树

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

/**
 * 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 boolean isSameTree(TreeNode p, TreeNode q) {
       //if(p==null&&q==null){return false;}
        return comparable(p,q);
    }

    public boolean comparable(TreeNode p,TreeNode q){
        if(p!=null&&q==null){return false;}
        else if(p==null&&q==null){return true;}
        else if(p==null&&q!=null){return false;}
        else if(p.val!=q.val){return false;}
        boolean a = comparable(p.left,q.left);
        boolean b = comparable(p.right,q.right);
        return a && b;
    }
}



572. 另一棵树的子树

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

/**
 * 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 boolean isSubtree(TreeNode root, TreeNode subRoot) {
        //前序遍历root
        List<TreeNode> nodes = new ArrayList<>();
        preorder(root,nodes);
        for (TreeNode node : nodes) {
            //此时nodes里面是root中的所有结点
            if(comparable(node, subRoot)){
                return true;
            }
        }
        return false;
    }
    public void preorder(TreeNode root, List<TreeNode> nodes){
        if(root==null){return ;}
        nodes.add(root);
        preorder(root.left,nodes);
        preorder(root.right,nodes);
    }
    
    public boolean comparable(TreeNode left,TreeNode right){
        if(left==null&&right==null){return true;}
        else if(left!=null&&right==null){return false;}
        else if(left==null&&right!=null){return false;}
        else if(left.val!= right.val){return false;}
        boolean a = comparable(left.left, right.left);
        boolean b = comparable(left.right, right.right);
        return a && b;
    }
}



104. 二叉树的最大深度

  • 这题昨天用层序遍历写过，下面是递归的实现：
/**
 * 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 int maxDepth(TreeNode root) {
        //这里用根结点的高度表示二叉树的最大深度
        if(root==null){return 0;}
        int leftDepth = maxDepth(root.left);//左孩子的高度
        int rightDepth = maxDepth(root.right);//右孩子的高度
        return Math.max(leftDepth,rightDepth)+1;//当前结点的高度（左孩子的高度，右孩子的高度的最大值+1）
        //后序遍历
    }
}
  • 感觉递归还是不太好理解


559. N 叉树的最大深度

给定一个 N 叉树，找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    public int maxDepth(Node root) {
        if(root==null){return 0;}
        List<Node> children = root.children;//当前结点的孩子们
        int max = 0;
        for (Node child : children) {
            int depth = maxDepth(child);
            max = Math.max(depth,max);
        }
        return max+1;
    }
}
  • 扩展成n叉树，和二叉树区别不大，就是孩子数不确定，用for循环遍历求孩子的高度就好



111. 二叉树的最小深度

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

ψ(｀∇´)ψ 我的思路

  • 稍微改了二叉树最大深度的代码，
/**
 * 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 int minDepth(TreeNode root) {
        if(root==null){return 0;}//空的结点是第0层(也是递归出口)
        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);
        return Math.min(leftDepth,rightDepth)+1;
    }
}
  • 代码在运行下图例子时返回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;
 *     }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        if(root==null){return 0;}//空的结点是第0层(也是递归出口)
        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);
        if(root.left==null){return rightDepth+1;}//如果左子树为空，返回右子树的高度+1
        else if(root.right==null){return leftDepth+1;}//如果右子树为空，返回左子树的高度+1
        return Math.min(leftDepth,rightDepth)+1;
    }
}



222. 完全二叉树的节点个数

完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

ψ(｀∇´)ψ 我的思路

  • 层序遍历，每弹出一个数count++
/**
 * 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 int countNodes(TreeNode root) {
        Queue<TreeNode> que = new LinkedList<>();
        if(root==null){return 0;}
        int count = 0;
        que.add(root);
        while (!que.isEmpty()){
            int size = que.size();
            while (size>0){
                count++;
                TreeNode node = que.poll();
                if(node.left!=null){que.add(node.left);}
                if(node.right!=null){que.add(node.right);}
                size--;
            }
        }
        return count;
    }
}
  • 不知道是不是昨天层序遍历做多了，我现在拿到题想的都是层序遍历，递归好难想啊?
class Solution {
    // 还是展示递归解法（后序遍历）
    public int countNodes(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
}
  • 离谱离谱，就这么几行


110. 平衡二叉树

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

ψ(｀∇´)ψ 我的思路

  • 求出根结点左右子树的最大高度，相减取绝对值不超过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;
 *     }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root==null){return true;}
        int leftHeight = maxHeight(root.left);
        int rightHeight = maxHeight(root.right);
        if(Math.abs(leftHeight-rightHeight)<=1){
            return true;
        } else{return false;}
    }

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

  • 按我的思路，这就是个平衡二叉树，仔细读题后发现：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 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;
 *     }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        //后序遍历
        int height = getHeight(root);
        if(height==-1){return false;}
        else return true;
    }

   public int getHeight(TreeNode root){
        if(root==null){
            return 0;//null结点高度为0
        }
       int leftHeight = getHeight(root.left);//左子树的高度
       if(leftHeight==-1){return -1;}
       int rightHeight = getHeight(root.right);//右子树的高度
       if(rightHeight==-1){return -1;}
       if(Math.abs(leftHeight-rightHeight)>1){return -1;}//当前结点左右子树高度差>1
       return 1+Math.max(leftHeight,rightHeight);//返回当前结点的高度
    }
}
  • 递归，递归，又是你！！！


257. 二叉树的所有路径

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。

  • 这题用到了回溯，如下图
/**
 * 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<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();//结果列表
        if(root==null){return res;}
        List<Integer> path = new ArrayList<Integer>();//路径列表（存放经过结点的值）
        postOrder(root,path,res);
        return res;
    }

    public void postOrder(TreeNode node,List<Integer> path,List<String> res){
        path.add(node.val);//每一个结点都加在路径里面
        if(node.left==null&&node.right==null){//如果node没孩子（叶子节点）
            //就可以把path转换成String加到res中啦
            StringBuilder sb = new StringBuilder();
            for (Integer i : path) {
                sb.append(i+"->");
            }
            String s = sb.toString();
            s = s.substring(0,s.length()-2);//把最后一个->去掉
            res.add(s);
        }
       if (node.left != null) {
            postOrder(node.left, path, res);
            path.remove(path.size()-1);//回溯
        }
        if (node.right != null) {
            postOrder(node.right, path, res);
            path.remove(path.size()-1);//回溯
        }
    }
}
  • 这题挺好，标记。


404. 左叶子之和

给定二叉树的根节点 root ，返回所有左叶子之和。

  • 这题的突破点是找左叶子的定义：当一个结点的左孩子不空（无所谓右孩子）,且左孩子没孩子，即为左叶子。
/**
 * 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 int sumOfLeftLeaves(TreeNode root) {
        if(root==null){
            return 0;
        }
        int midValue = 0;//存储当前结点的左孩子的值
        if(root.left!=null&&root.left.left==null&&root.left.right==null){
            midValue = root.left.val;//如果root.left满足左叶子的条件
        }
        int leftValue = sumOfLeftLeaves(root.left);
        int rightValue = sumOfLeftLeaves(root.right);
        return midValue+leftValue+rightValue;//返回当前结点的值，加上左右孩子的叶子结点数
    }
}
  • 递归真的是不好想啊，感觉我现在的水平只能是看懂



513. 找树左下角的值

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。

ψ(｀∇´)ψ 我的思路

  • 层序遍历到最后一层，第一个弹出的值即为所求
/**
 * 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 int findBottomLeftValue(TreeNode root) {
         Queue<TreeNode> que = new LinkedList<>();
        List<Integer> list = null;
        que.add(root);
        while (!que.isEmpty()){//控制层数
            list = new ArrayList<>();
            int size = que.size();
            while (size>0){//控制每层的元素个数
                TreeNode node = que.poll();
                list.add(node.val);
                if(node.left!=null){que.add(node.left);}
                if(node.right!=null){que.add(node.right);}
                if(size==1){       
                }
                size--;
            }  
        }
        return list.get(0);//因为链表每层都刷新，所以此时链表记录的是最后一层的结点
    }
}
  • hhh，只要可以用层序遍历，我就是小神仙?


112. 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。

  • 感觉和上面的二叉树的所有路径很像，就改了一下上面的代码。第一遍的时候是自己写的，没有写出来。
/**
 * 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 boolean hasPathSum(TreeNode root, int targetSum) {
        List<Integer> res = new ArrayList<>();//用来存放所有路径的和
        if(root==null){return false;}
        List<Integer> path = new ArrayList<Integer>();//用来存放经过结点的值
        postOrder(root,path,res);
        if(res.contains(targetSum)){return true;}
        else return false;
    }

    public void postOrder(TreeNode node,List<Integer> path,List<Integer> res){
        path.add(node.val);//每一个结点的值都加在路径里面
        if(node.left==null&&node.right==null){//如果node没孩子（叶子节点）
            int sum = 0;
            for (Integer i : path) {
                sum += i;
            }
            res.add(sum); //求出当前路径的总和加到res中
        }
        if (node.left != null) {
            postOrder(node.left, path, res);
            path.remove(path.size()-1);//回溯
        }
        if (node.right != null) {
            postOrder(node.right, path, res);
            path.remove(path.size()-1);//回溯
        }
    }
}



113. 路径总和 II

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。

ψ(｀∇´)ψ 我的思路

  • 还是路径的问题，我就按路径的模板写了一下，但是在debug的时候发现res会随着path的改变而改变。活见鬼?，我明明已经把path加到res里了。
/**
 * 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<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<>();//结果列表
        List<Integer> path = new ArrayList<>();//路径列表
        if(root==null){return res;}
        path(root,path,res,targetSum);
        return res;
    }

    void path(TreeNode node,List<Integer> path,List<List<Integer>> res,int targetSum){
        path.add(node.val);
        if(node.left==null&&node.right==null){//到达了叶子结点
            int sum = 0;
            for (Integer i : path) {
                sum+=i;
            }
            if(sum==targetSum){res.add(path);}
        }
       if (node.left != null) {
            path(node.left, path, res, targetSum);
            path.remove(path.size()-1);//回溯
        }
        if (node.right != null) {
            path(node.right, path, res, targetSum);
            path.remove(path.size()-1);//回溯
        }
    }
}
  • 但仔细一想应该是递归的问题，我找不到解决的方法，看了题解后发现其实就是一行代码
 if(sum==targetSum){ res.add(new ArrayList<>(path));}
  • 活见鬼?,刚开始看的时候我就不相信这是java的语法，我就没见过泛型后面的小括号里面放东西?，但是运行通过。网上也找不到靠谱的解释，我猜是新建了一个与path相同类型的链表把path装了进来，这样我再debug，res就不会随着递归变化了。

❗标记，标记，这一题不太会



106. 从中序与后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

确认过眼神，是我写不出来的题目?

  • 思路是不难理解的

    步骤：
  1. 判断后序数组是否为空
  2. 取后序数组的最后一个值的下标切割中序数组，把中序数组切割成左中序和右中序
  3. 用两个区间的长度去切割后序数组，得到左后序和右后序
  4. 递归（左中序，左后序），递归（右中序，右后序）
/**
 * 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 {
    Map<Integer, Integer> map;  // 方便根据数值查找位置
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置
            map.put(inorder[i], i);
        }
        return findNode(inorder,  0, inorder.length, postorder,0, postorder.length);  // 前闭后开
    }
    
    public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
        // 参数里的范围都是前闭后开
        if (inBegin >= inEnd || postBegin >= postEnd) {  // 不满足左闭右开，说明没有元素，返回空树
            return null;
        }
        int rootIndex = map.get(postorder[postEnd - 1]);  // 找到后序遍历的最后一个元素在中序遍历中的位置
        TreeNode root = new TreeNode(inorder[rootIndex]);  // 构造结点
        int lenOfLeft = rootIndex - inBegin;  // 保存中序左子树个数，用来确定后序数列的个数
        root.left = findNode(inorder, inBegin, rootIndex, postorder, postBegin, postBegin + lenOfLeft);
        root.right = findNode(inorder, rootIndex + 1, inEnd, postorder, postBegin + lenOfLeft, postEnd - 1);
        return root;
    }
}
  • ❗ 标记，标记，这题不是自己写的



105. 从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

  • 与上一题类似，改了一下上一题的代码
/**
 * 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 {
    Map<Integer, Integer> map;  // 方便根据数值查找位置
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置
            map.put(inorder[i], i);
        }
        return findNode(inorder,  0, inorder.length, preorder,0, preorder.length);  // 前闭后开
    }
    
    public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] preorder, int preBegin, int preEnd) {
        // 参数里的范围都是前闭后开
        if (inBegin >= inEnd || preBegin >= preEnd) {  // 不满足左闭右开，说明没有元素，返回空树
            return null;
        }
        int rootIndex = map.get(preorder[preBegin]);  // 找到前序遍历的最后一个元素在中序遍历中的位置
        TreeNode root = new TreeNode(inorder[rootIndex]);  // 构造结点
        int lenOfLeft = rootIndex - inBegin;  // 保存中序左子树个数，用来确定前序数列的个数
        root.left = findNode(inorder, inBegin, rootIndex, preorder, preBegin+1, preBegin + lenOfLeft+1);
        root.right = findNode(inorder, rootIndex + 1, inEnd, preorder, preBegin + lenOfLeft+1, preEnd);
        return root;
    }
}
  • 太残忍了，太残忍了，最后这两题，就是在屠杀我的脑细胞?，不知道看多少集海绵宝宝才能养回来



总结


  • 今天的题比昨天的题要好，每一道题都很有代表性?

  • 翻转二叉树：交换结点指向左右孩子的指针

  • 对称二叉树：以根结点所在竖直线为对称轴，先比较外侧结点，后比较内侧结点（相同的树，另一棵树的子树类似）（有点像双指针

  • 二叉树的最大深度：求二叉树的最大深度就是求根结点的高度，求高度用后序遍历，当前结点的高度是左右孩子高度的最大值+1（N叉树的最大深度类似）

  • 二叉树的最小深度：如果左子树为空，当前结点的高度为右子树的高度+1；如果右子树为空，当前结点的高度为左子树的高度+1，画个图你就知道啦?

  • 完全二叉树的结点个数：基础的遍历题

  • 平衡二叉树：求高度的题，要用后序遍历

  • 二叉树的所有路径：求路径的题，要用到回溯，需要什么条件就往递归方法中加参数就可

  • 左叶子之和：关键是判断左叶子

  • 找树左下角的值：层序遍历

  • 路径总和：改路径题的模板（其实还是有点迷的，尤其是递归方法带参数，好家伙，那是一个千变万化，根本分析不出来?）

  • 从中/前序后序遍历序列构造二叉树，重点在区间的划分

  • 遇到问题总是先想层序遍历，但是感觉递归才是正统解法，要好好掌握递归才行

  • 做了一天的二叉树，现在感觉我就是个二叉树?

随想录代码TreeNoderightleft算法与数据结构

有关代码随想录 | 二叉树的更多相关文章

  1. ruby - 如何在 buildr 项目中使用 Ruby 代码？ - 2

    如何在buildr项目中使用Ruby？我在很多不同的项目中使用过Ruby、JRuby、Java和Clojure。我目前正在使用我的标准Ruby开发一个模拟应用程序，我想尝试使用Clojure后端(我确实喜欢功能代码)以及JRubygui和测试套件。我还可以看到在未来的不同项目中使用Scala作为后端。我想我要为我的项目尝试一下buildr(http://buildr.apache.org/)，但我注意到buildr似乎没有设置为在项目中使用JRuby代码本身!这看起来有点傻，因为该工具旨在统一通用的JVM语言并且是在ruby中构建的。除了将输出的jar包含在一个独特的、仅限ruby​​

  2. ruby-on-rails - Rails 源代码 : initialize hash in a weird way? - 2

    在rails源中:https://github.com/rails/rails/blob/master/activesupport/lib/active_support/lazy_load_hooks.rb可以看到以下内容@load_hooks=Hash.new{|h,k|h[k]=[]}在IRB中，它只是初始化一个空哈希。和做有什么区别@load_hooks=Hash.new 最佳答案 查看rubydocumentationforHashnew→new_hashclicktotogglesourcenew(obj)→new_has

  3. ruby-on-rails - 浏览 Ruby 源代码 - 2

    我的主要目标是能够完全理解我正在使用的库/gem。我尝试在Github上从头到尾阅读源代码，但这真的很难。我认为更有趣、更温和的踏脚石就是在使用时阅读每个库/gem方法的源代码。例如，我想知道RubyonRails中的redirect_to方法是如何工作的:如何查找redirect_to方法的源代码？我知道在pry中我可以执行类似show-methodmethod的操作，但我如何才能对Rails框架中的方法执行此操作？您对我如何更好地理解Gem及其API有什么建议吗？仅仅阅读源代码似乎真的很难，尤其是对于框架。谢谢! 最佳答案 Ru

  4. ruby - 模块嵌套代码风格偏好 - 2

    我的假设是moduleAmoduleBendend和moduleA::Bend是一样的。我能够从thisblog找到解决方案,thisSOthread和andthisSOthread.为什么以及什么时候应该更喜欢紧凑语法A::B而不是另一个，因为它显然有一个缺点？我有一种直觉，它可能与性能有关，因为在更多命名空间中查找常量需要更多计算。但是我无法通过对普通类进行基准测试来验证这一点。 最佳答案 这两种写作方法经常被混淆。首先要说的是，据我所知，没有可衡量的性能差异。(在下面的书面示例中不断查找)最明显的区别，可能也是最著名的，是你的

  5. ruby - 寻找通过阅读代码确定编程语言的ruby gem？ - 2

    几个月前，我读了一篇关于ruby​​gem的博客文章，它可以通过阅读代码本身来确定编程语言。对于我的生活，我不记得博客或gem的名称。谷歌搜索“ruby编程语言猜测”及其变体也无济于事。有人碰巧知道相关gem的名称吗？ 最佳答案 是这个吗:http://github.com/chrislo/sourceclassifier/tree/master 关于ruby-寻找通过阅读代码确定编程语言的rubygem？，我们在StackOverflow上找到一个类似的问题：

  6. ruby - Net::HTTP 获取源代码和状态 - 2

    我目前正在使用以下方法获取页面的源代码:Net::HTTP.get(URI.parse(page.url))我还想获取HTTP状态，而无需发出第二个请求。有没有办法用另一种方法做到这一点？我一直在查看文档，但似乎找不到我要找的东西。 最佳答案 在我看来，除非您需要一些真正的低级访问或控制，否则最好使用Ruby的内置Open::URI模块:require'open-uri'io=open('http://www.example.org/')#=>#body=io.read[0,50]#=>"["200","OK"]io.base_ur

  7. 程序员如何提高代码能力？ - 2

    前言作为一名程序员，自己的本质工作就是做程序开发，那么程序开发的时候最直接的体现就是代码，检验一个程序员技术水平的一个核心环节就是开发时候的代码能力。众所周知，程序开发的水平提升是一个循序渐进的过程，每一位程序员都是从“菜鸟”变成“大神”的，所以程序员在程序开发过程中的代码能力也是根据平时开发中的业务实践来积累和提升的。提高代码能力核心要素程序员要想提高自身代码能力，尤其是新晋程序员的代码能力有很大的提升空间的时候，需要针对性的去提高自己的代码能力。提高代码能力其实有几个比较关键的点，只要把握住这些方面，就能很好的、快速的提高自己的一部分代码能力。1、多去阅读开源项目，如有机会可以亲自参与开源

  8. 7个大一C语言必学的程序 / C语言经典代码大全 - 2

    嗨~大家好，这里是可莉！今天给大家带来的是7个C语言的经典基础代码~那一起往下看下去把【程序一】打印100到200之间的素数#includeintmain(){ inti; for(i=100;i 【程序二】输出乘法口诀表#includeintmain(){inti;for(i=1;i 【程序三】判断1000年---2000年之间的闰年#includeintmain(){intyear;for(year=1000;year 【程序四】给定两个整形变量的值，将两个值的内容进行交换。这里提供两种方法来进行交换，第一种为创建临时变量来进行交换，第二种是不创建临时变量而直接进行交换。1.创建临时变量来

  9. git使用常见问题（提交代码，合并冲突） - 2

    文章目录git常用命令（简介，详细参数往下看）Git提交代码步骤gitpullgitstatusgitaddgitcommitgitpushgit代码冲突合并问题方法一：放弃本地代码方法二：合并代码常用命令以及详细参数gitadd将文件添加到仓库：gitdiff比较文件异同gitlog查看历史记录gitreset代码回滚版本库相关操作远程仓库相关操作分支相关操作创建分支查看分支：gitbranch合并分支：gitmerge删除分支：gitbranch-ddev查看分支合并图：gitlog–graph–pretty=oneline–abbrev-commit撤消某次提交git用户名密码相关配置g

  10. ruby - 这两段代码有什么区别？ - 2

    打印1:defsum(i)i=i+[2]end$x=[1]sum($x)print$x打印12:defsum(i)i.push(2)end$x=[1]sum($x)print$x后者是修改全局变量$x。为什么它在第二个例子中被修改而不是在第一个例子中？类Array的任何方法(不仅是push)都会发生这种情况吗？ 最佳答案 变量范围在这里无关紧要。在第一段代码中，您仅使用赋值运算符=为变量i赋值，而在第二段代码中，您正在修改$x(也称为i)使用破坏性方法push。赋值从不修改任何对象。它只是提供一个名称来引用一个对象。方法要么是破坏性

随机推荐