这篇文章上次修改于 216 天前,可能其部分内容已经发生变化,如有疑问可询问作者。

No.1 二叉树的最大深度

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

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

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

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

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。


两种方法尝试,从上到下,从下到上

从上到下来写

没想到最后还是要多写个函数,不过下面的算法倒是完全手撸的,感觉还可以。。而输入为

[] 而且用递归只能写辅助函数?有点头秃

Result

`我的提交执行用时
已经战胜 100.00 % 的 java 提交记录`

/**
 * 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;
        else
            return helpDepth(root);
    }
    
    public int helpDepth(TreeNode root) {
         int RL = 0;
         int CL = 0;
        if(root.left == null && root.right == null)
            return 1;
        if(root.left != null)
            RL = helpDepth(root.left);
        if(root.right != null)
            CL = helpDepth(root.right);
        return RL > CL ? RL + 1: CL + 1;
    }
}

No.2 对称二叉树

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

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

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

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3

进阶:

你可以运用递归和迭代两种方法解决这个问题吗?

递归

就是判断镜子嘛,其实这题之前看过题解,现在映像不深了,几天前的事情了,那么争取手撸出来

自己手写就感觉像在搭积木,不断的改错,重试

Result

`执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗 :38 MB, 在所有 Java 提交中击败了28.75%的用户`

/**
 * 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;
        // 如果左右不存在
        if((root.left == null && root.right != null) || (root.left != null && root.right == null))
            return false;
        return helpSymmetric(root.left, root.right);
    }
    
    public boolean helpSymmetric(TreeNode left, TreeNode right)
    {
        boolean l1 = true;
        boolean l2 = true;
        // 如果两者..
        if((left == null && right != null) || (left != null && right == null))
            return false;
        // 再次排除一个条件
        if(right == null && left == null)
            return true;
        // 最后如果值不相等
        if(left.val != right.val)
            return false;
        // 返回左右得到的
        l1 = helpSymmetric(left.right, right.left);
        l2 = helpSymmetric(left.left, right.right);
        return l1 && l2;
    }
}

迭代

先放着

No.3 路径总和

给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。

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

示例:
给定如下二叉树,以及目标和 sum = 22

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2


感觉这题有点挑战性

Reuslt

`我的提交执行用时
已经战胜 100.00 % 的 java 提交记录`

结果上来看,还不错

手撸

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    // 总标记
    boolean flag = false;
    public boolean hasPathSum(TreeNode root, int sum) {
           if(root == null)
              return flag;
           int s = 0;
           sum(root, s, sum);
           return flag;
    }
    // 辅助求和函数
    public void sum(TreeNode root, int s, int sum)
    {
        s += root.val;
           if(root.left == null &&  root.right == null)
        {
            if(sum == s)
            {
                flag == true;
            }
        }
        if(root.left != null)
            sum(root.left, s, sum);
        if(root.right != null)
            sum(root.right, s, sum);
    }
}

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

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

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

例如,给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树:

    3
   / \
  9  20
    /  \
   15   7

分析

后序最后一个必然是根节点

中序根节点前必然是左子树

后序左子树和根节点中间必然是右子树

截取出子树片段,根据相应法则进行构建,然后连上根节点上

使用辅助函数(IDEA上写,这次就不直接markdown手撸了,有些函数还是不熟)

放弃,tnl

package leetcode.tree;

import java.util.*;

class Tree{
    int val;
    TreeNode left;
    TreeNode right;
    Tree(int x) { val = x; }
}

public class buildTree_03 {
    public Tree buildTree(int[] inorder, int[] postorder) {
        // 先找出根节点
        int root_val = postorder[postorder.length - 1];
        // 创建根节点
        Tree root = new Tree(root_val);
        // 找出根节点中在 inorder上的位置,找出左子树所有点
        List<Integer> list = new ArrayList<>();
        for (Integer c : inorder)
            list.add(c);
        // 左
        list.indexOf(root_val);
        List<Integer> list1 = list.subList(0, list.indexOf(root_val));
        // 右
        List<Integer> list2 = list.subList(list.indexOf(root_val) + 1, list.size());
    }

    // 中序是 左中右,其创建
    public  Tree help(List<Integer> list, Tree root)
    {
        Tree node = null;
        node.val = list.get(0);
        
    }
}

官解

传送门

class Solution {
  int post_idx;
  int[] postorder;
  int[] inorder;
  HashMap<Integer, Integer> idx_map = new HashMap<Integer, Integer>();

  public TreeNode helper(int in_left, int in_right) {
    // if there is no elements to construct subtrees
    if (in_left > in_right)
      return null;

    // pick up post_idx element as a root
    int root_val = postorder[post_idx];
    TreeNode root = new TreeNode(root_val);

    // root splits inorder list
    // into left and right subtrees
    int index = idx_map.get(root_val);

    // recursion 
    post_idx--;
    // build right subtree
    root.right = helper(index + 1, in_right);
    // build left subtree
    root.left = helper(in_left, index - 1);
    return root;
  }

  public TreeNode buildTree(int[] inorder, int[] postorder) {
    this.postorder = postorder;
    this.inorder = inorder;
    // start from the last postorder element
    post_idx = postorder.length - 1;

    // build a hashmap value -> its index
    int idx = 0;
    for (Integer val : inorder)
      idx_map.put(val, idx++);
    return helper(0, inorder.length - 1);
  }
}

Today is over