LeetCode 树专题

2020/01/22 Prolems

目录

101. 对称二叉树 简单

  • 题目描述

    给定一个二叉树,检查它是否是镜像对称的。

    例如,二叉树 [1,2,2,3,4,4,3] 是对称的。

    Example:

  • 解法

    一直递归判断左子树的左子树是否等于右子树的右子树,左子树的右子树是否等于右子树的左子树。

  • 代码

      /**
      * Definition for a binary tree node.
      * public class TreeNode {
      *     int val;
      *     TreeNode left;
      *     TreeNode right;
      *     TreeNode(int x) { val = x; }
      * }
      */
      class Solution {
          public boolean isSymmetric(TreeNode root) {
              if(root==null) return true;
              return isSymmetricHelper(root.left,root.right);
          }
          public boolean isSymmetricHelper(TreeNode left, TreeNode right) {
              if(left==null&&right==null) return true;
              if(left==null||right==null) return false;
              if(left.val!=right.val) return false;
              return isSymmetricHelper(left.left,right.right) && isSymmetricHelper(left.right,right.left);
          }
      }
    

104. 二叉树的最大深度 简单

  • 题目描述

    给定一个二叉树,找出其最大深度。

    二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

    **说明: **叶子节点是指没有子节点的节点。

    Example:

  • 解法

    递归,取左右子树的最大深度并加一。

  • 代码

      /**
      * Definition for a binary tree node.
      * public class TreeNode {
      *     int val;
      *     TreeNode left;
      *     TreeNode right;
      *     TreeNode(int x) { val = x; }
      * }
      */
      class Solution {
          public int maxDepth(TreeNode root) {
              if(root==null) return 0;
              return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
          }
      }
    

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

  • 题目描述

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

    注意:

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

    Example:

  • 解法

    前序遍历数组的第一个值是根节点,可以那根节点找到中序遍历时对应的值,也就得出了左子树的长度。那总长度 - 左子树长度 - 1 也就是右子树长度,也就可以递归了。

  • 代码

      /**
      * Definition for a binary tree node.
      * public class TreeNode {
      *     int val;
      *     TreeNode left;
      *     TreeNode right;
      *     TreeNode(int x) { val = x; }
      * }
      */
      class Solution {
          public TreeNode buildTree(int[] preorder, int[] inorder) {
              if(preorder.length==0) return null;
              return helper(preorder,inorder,0,0,preorder.length);
          }
          public TreeNode helper(int[] preorder, int[] inorder, int preBegin, int inBegin, int length){
              if(length==0) return null;
              if(length==1){
                  return new TreeNode(preorder[preBegin]);
              }
              int value = preorder[preBegin];
              int thisEnd = inBegin;
              for(;thisEnd<inBegin+length-1;thisEnd++){
                  if(inorder[thisEnd]==value){
                      break;
                  }
              }
              TreeNode node = new TreeNode(value);
              node.left = helper(preorder,inorder,preBegin+1,inBegin,thisEnd-inBegin);
              node.right = helper(preorder,inorder,preBegin+thisEnd-inBegin+1,thisEnd+1,length-(thisEnd-inBegin)-1);
              return node;
          }
      }
    

236. 二叉树的最近公共祖先 中等

  • 题目描述

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

    注意:

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

    Example:

  • 解法

    从跟节点往下 dfs 递归。如果遇到等同于一个节点,证明找到,返回这个节点。当左右都找到,此时返回这个跟节点即最低公共节点。只找到左/右有可能是已经找到了最低节点(是他的子节点),或者这一半只有一个,另一个在他跟节点的另一个枝上所以返回节点。

  • 代码

      /**
      * Definition for a binary tree node.
      * public class TreeNode {
      *     int val;
      *     TreeNode left;
      *     TreeNode right;
      *     TreeNode(int x) { val = x; }
      * }
      */
      class Solution {
          public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
              if(root == null){
                  return null;
              }
              if(root==p||root==q){
                  return root;
              }
              TreeNode left = lowestCommonAncestor(root.left,p,q);
              TreeNode right = lowestCommonAncestor(root.right,p,q);
              if(left!=null&&right!=null){
                  return root;
              }
              if(left!=null){
                  return left;
              }else{
                  return right;
              }
          }
      }
    

543. 二叉树的直径 简单

  • 题目描述

    给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。

    Example:

  • 解法

    直径就是左右子树最大深度相加,但是要注意效率,可以在每次求最大深度时就把左右子树相加看看当前最大深度。这样同时进行避免重复计算。

  • 代码

      /**
      * Definition for a binary tree node.
      * public class TreeNode {
      *     int val;
      *     TreeNode left;
      *     TreeNode right;
      *     TreeNode(int x) { val = x; }
      * }
      */
      class Solution {
          int max = 0;
          public int diameterOfBinaryTree(TreeNode root) {
              depth(root);
              return max;
          }
          public int depth(TreeNode root){
              if(root == null) return 0;
              int left = depth(root.left);
              int right = depth(root.right);
              max = Math.max(left+right,max);
              return 1+Math.max(left,right);
          }
      }
    

124. 二叉树中的最大路径和 困难

  • 题目描述

    给定一个非空二叉树,返回其最大路径和。

    本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。

    Example:

      输入: [-10,9,20,null,null,15,7]
    
       -10
       / \
      9  20
        /  \
       15   7
    
      输出: 42
    
  • 解法

    与上一题求直径类似,只不过是把每次深度 +1 变成了加上当前节点的值。但要注意负数的情况,如果左右节点是负数那就舍弃设为 0。

  • 代码

      /**
      * Definition for a binary tree node.
      * public class TreeNode {
      *     int val;
      *     TreeNode left;
      *     TreeNode right;
      *     TreeNode(int x) { val = x; }
      * }
      */
      class Solution {
          int max = Integer.MIN_VALUE;
          public int maxPathSum(TreeNode root) {
              max(root);
              return max;
          }
          public int max(TreeNode root){
              if(root == null) return 0;
              int left = max(root.left);
              int right = max(root.right);
              left = left<0?0:left;
              right = right<0?0:right;
              max= Math.max(max,root.val+left+right);
              return root.val+Math.max(left,right);
          }
      }
    

117. 填充每个节点的下一个右侧节点指针 II 中等

  • 题目描述

    填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。

    初始状态下,所有 next 指针都被设置为 NULL。

    Example:

    tree

  • 解法

    这里只说最简单的方法,用 queue 做广度搜索,记录每一行的数量和上一个节点。只要不是新的一行的第一个,就把上一个节点的下一个设为当前节点。

  • 代码

      /*
      // Definition for a Node.
      class Node {
          public int val;
          public Node left;
          public Node right;
          public Node next;
    
          public Node() {}
            
          public Node(int _val) {
              val = _val;
          }
    
          public Node(int _val, Node _left, Node _right, Node _next) {
              val = _val;
              left = _left;
              right = _right;
              next = _next;
          }
      };
      */
      class Solution {
          public Node connect(Node root) {
              if(root==null) return null;
              LinkedList<Node> queue = new LinkedList<>();
              queue.offer(root);
              while(!queue.isEmpty()){
                  int size = queue.size();
                  Node pre = null;
                  for(int i=0;i<size;i++){
                      Node node = queue.poll();
                      if(i>0){
                          pre.next = node;
                      }
                      if(node.left!=null) queue.offer(node.left);
                      if(node.right!=null) queue.offer(node.right);
                      pre = node;
                  }
              }
              return root;
          }
      }
    

337. 打家劫舍 III 中等

  • 题目描述

    在上次打劫完一条街道之后和一圈房屋后,小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为“根”。 除了“根”之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫,房屋将自动报警。

    计算在不触动警报的情况下,小偷一晚能够盗取的最高金额。

    Example:

      输入: [3,4,5,1,3,null,1]
    
           3
          / \
         4   5
        / \   \ 
       1   3   1
    
      输出: 9
      解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.
    
  • 解法

    最大值可能有两种,取当前节点,然后再取就得是下下个节点或者不取当前节点,取当前的下一个节点。从这两种情况中取最大值。

  • 代码

      /**
      * Definition for a binary tree node.
      * public class TreeNode {
      *     int val;
      *     TreeNode left;
      *     TreeNode right;
      *     TreeNode(int x) { val = x; }
      * }
      */
      class Solution {
          Map<TreeNode,Integer> map = new HashMap<>(); //用一个 map 存储中间变量加速
          public int rob(TreeNode root) {
              if(map.containsKey(root)){
                  return map.get(root);
              }
              if(root==null) return 0;
              int value = root.val; //当前节点算进去
              int value2 = 0; //当前节点不要
              if(root.left!=null){
                  value+=rob(root.left.left)+rob(root.left.right);
                  value2+=rob(root.left);
              }
              if(root.right!=null){
                  value+=rob(root.right.left)+rob(root.right.right);
                  value2+=rob(root.right);
              }
              int res = Math.max(value,value2);
              map.put(root,res);
              return res;
          }
      }
    

199. 二叉树的右视图 中等

  • 题目描述

    给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。

    Example:

  • 解法

    层次遍历,将每一层的最后一个值输入到结果中。

  • 代码

      /**
      * Definition for a binary tree node.
      * public class TreeNode {
      *     int val;
      *     TreeNode left;
      *     TreeNode right;
      *     TreeNode(int x) { val = x; }
      * }
      */
      class Solution {
          Map<TreeNode,Integer> map = new HashMap<>(); //用一个 map 存储中间变量加速
          public int rob(TreeNode root) {
              if(map.containsKey(root)){
                  return map.get(root);
              }
              if(root==null) return 0;
              int value = root.val; //当前节点算进去
              int value2 = 0; //当前节点不要
              if(root.left!=null){
                  value+=rob(root.left.left)+rob(root.left.right);
                  value2+=rob(root.left);
              }
              if(root.right!=null){
                  value+=rob(root.right.left)+rob(root.right.right);
                  value2+=rob(root.right);
              }
              int res = Math.max(value,value2);
              map.put(root,res);
              return res;
          }
      }
    

Search

    Table of Contents