Leetcode – 探索 – 树篇 – 进阶

发布于 17 天前  6 次阅读 本文共6049个字


总结

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

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

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

例如,给出

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

返回如下的二叉树:

    3
   / \
  9  20
    /  \
   15   7

思路

中序遍历是 左中右,后序遍历是左右中,这样可以直接先拿出后序的根,然后切分中序遍历,第一个点,一定是最左边,

。。然后5分钟过去了,还是没解决。。

 // 从中序和后序遍历序列中构造二叉树
    // 中序遍历 inorder = [9,3,15,20,7]
    // 后序遍历 postorder = [9,15,7,20,3]
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        // 找出根结点,先构造一个树
        TreeNode root = new TreeNode(postorder[postorder.length - 1]);
        // 然后切分中序遍历
        List<Integer> left_inorder = new ArrayList<>();
        List<Integer> right_inorder = new ArrayList<>();
        // 切分后序遍历
        int center = 0;
        for (int i = 0; i < inorder.length; i++)
        {
            if (inorder[i] == root.val)
            {
            }
        }

    }

参考

  1. 这个得建立辅助函数

  2. 构建出左子树,右子树

  3. 划分子问题,然后递归的构建左子树和右子树。

class Solution {
  public TreeNode buildTree(int[] inorder, int[] postorder) {
        return helper(inorder, postorder, postorder.length - 1, 0, inorder.length - 1);
    }

    private  TreeNode helper(int [] inorder, int [] postorder, int postEnd, int inStart, int inEnd)
    {
        // 如果为空树
        if (inStart > inEnd)
            return null;

        // 不为空树,根据后序特点,得到根结点
        int currentVal = postorder[postEnd];

        TreeNode current = new TreeNode(currentVal);

        // 找到根结点值在中序数组中的下标位置
        int inIndex = 0;
        for (int i = inStart; i <= inEnd; i++){
            if (inorder[i] == currentVal)
                inIndex = i;
        }

        // 构建左子树
        TreeNode left = helper(inorder, postorder, postEnd - (inEnd - inIndex) - 1, inStart, inIndex - 1);
        // 构建右子树  4 - 1  = 3 - 1 = 2        0 +   
        TreeNode right = helper(inorder, postorder, postEnd -1, inIndex + 1, inEnd);


        // 连接
        current.left = left;
        current.right = right;

        return current;
    }
}

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

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

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

模仿练手

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

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

例如,给出

3 0 - 1

返回如下的二叉树:

    3
   / \
  9  20
    /  \
   15   7

思路

  1. 先建立辅助函数
  2. 按着前面来,好像出问题了
/**
 * 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) {
        return helper_pre(preorder, inorder, 0, 0, inorder.length - 1);
    }

    private TreeNode helper_pre(int[] preorder, int [] inorder, int preStart, int inStart, int inEnd)
    {
        // 判断是否为空树
        if (inStart > inEnd)
            return null;

        // 得到根结点
        TreeNode current = new TreeNode(preorder[preStart]);

        int inIndex = 0;
        // 得到根结点在中序中的坐标
        for (int i = inStart; i <= inEnd; i++)
        {
            if (inorder[i] == preorder[preStart])
            {
                inIndex = i;
            }
        }

        // 构建左子树
        TreeNode left = helper_pre(preorder, inorder, preStart + 1, inStart, inIndex - 1);
        // 构建右子树
        TreeNode right = helper_pre(preorder, inorder, inIndex + 1, inIndex + 1, inEnd);

        current.left = left;
        current.right = right;

        return current;
    }
}

Index 5 out of bounds of length 5 => 花几分钟改了后 => 超出内存限制

参考

因此,我们首先要得到从前序序列中获取根节点,然后遍历中序序列,找到根节点的位置,以此直到其左子树和右子树的范围。

当我得到其左子树之后,事情就开始重复了,我们仍然需要根据前序序列中找到这颗左子树的根节点,然后再根据中序序列得到这颗左子树根节点的左右子树。。。。右子树同理。

因此实际上就是个回溯。

解惑

原来,得到右子树在前序的下标,需要先计算左子树的个数。。。

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

    private TreeNode helper_pre(int[] preorder, int [] inorder, int preStart, int inStart, int inEnd)
    {
        // 判断是否为空树
        if (inStart > inEnd)
            return null;

        // 得到根结点
        TreeNode current = new TreeNode(preorder[preStart]);

        int inIndex = 0;
        // 得到根结点在中序中的坐标
        for (int i = inStart; i <= inEnd; i++)
        {
            if (inorder[i] == preorder[preStart])
            {
                inIndex = i;
            }
        }

        // 得到当前左子树个数
        int numLeft = inIndex - inStart;

        // 构建左子树
        TreeNode left = helper_pre(preorder, inorder, preStart + 1, inStart, inIndex - 1);
        // 构建右子树
        TreeNode right = helper_pre(preorder, inorder,  preStart  + 1 + numLeft, inIndex + 1, inEnd);

        current.left = left;
        current.right = right;

        return current;
    }
}

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

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

填充每个节点的下一个右侧节点指针

给定一个完美二叉树,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

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

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

示例:

img

输入:{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}

输出:{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1}

解释:给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。

提示:

  • 你只能使用常量级额外空间。
  • 使用递归解题也符合要求,本题中递归程序占用的栈空间不算做额外的空间复杂度。

思路

观测题目,有2个位置需要注意,其一是中间,其二是最右边,那么中间如何解呢?运用部分镜像知识,总的来说,这题分为三块

  1. 常规左右
  2. 越多级左右 = 》 镜像
  3. 最右边 null

ps. 想不出来,感觉这种方法不行

参考 - 大佬的解

/*
// 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 root;
        }
        // 如果左子树不为空
        if(root.left != null)
            root.left.next = root.right;
        // 如果右子树不为空
        if(root.right != null)
            root.right.next = root.next != null ? root.next.left : null;
            // wc,牛B,这个想法,确实顶。继承,!!!!
        // 开始递归
        connect(root.left);
        connect(root.right);
        // Over
        return root;
    }
}

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

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

填充每个节点的下一个右侧节点指针 II

示例:

class Solution {
    public Node connect(Node root) {
        // 如果为空
        if (root == null)
            return root;
        // 如果左不为空
        if (root.left != null)
            root.left.next = root.right != null ? root.right :(root.next !=null?(root.next.left != null? root.next.left:(root.next.right!=null?root.next.right:null)):null);
        // 如果右不为空
        if (root.right != null)
            root.right.next = root.next !=null?(root.next.left != null? root.next.left:(root.next.right!=null?root.next.right:null)):null;

        // 递归
        connect(root.left);
        connect(root.right);
        return root;
    }
}

出了大问题,这样写,如果右边很多 next 就没照顾到了,不能按照完全二叉树那样

GG

参考

没看懂,之后继续看

/*
// 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) {
       Node head = root;
      while (head != null){
          Node level = new Node();
          Node tail = level;
          while (head != null){
              if (head.left != null)
              {
                tail.next = head.left;
                tail = tail.next;
              }
              if (head.right != null){
                  tail.next = head.right;
                  tail = tail.next;
              }
              head = head.next;
          }
          head = level.next;
      }
      return root;
    }
}

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

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


粉色的花瓣,美丽地缠绕在身上。依在风里。