树的遍历 之 填充每个节点的下一个右侧节点指针|刷题打卡

作者: 稀土掘金  更新时间:2021-04-11 16:13:03  原文链接


本文正在参与掘金团队号上线活动,点击查看大厂春招职位

一、题目描述:

这个题目说的是,给你一棵满二叉树,每个树节点额外增加一个 next 指针,指向它右边的节点。

一开始所有节点的 next 指针都为空,你要写一个函数处理这棵二叉树,使得所有节点的 next 指针都指向正确的节点。

注意,满二叉树中,所有叶子节点都在最后一层。并且除了叶子节点,所有其他节点都有两个子节点。

// 包含 next 指针的树节点定义
public class Node {
  public int val;
  public Node left, right, next;
}

比如说,给你的满二叉树是:

     0
   /   \
  2     4
 / \   / \
6   8 10  12

一开始每个节点的 next 指针都为空。你要做的就是,让每个节点的 next 指针指向它右边的节点。
对于每一层中最后一个节点,由于它右边没有节点,因此它的 next 指针仍然指向空即可。

      0 -> null
   /     \
  2  ->   4 -> null
 / \     / \
6-> 8->10-> 12 -> null

二、思路分析:

这道题考察的树的遍历。

思路:

  1. BFS ,用一个队列记住每层长度,然后确定关系
  2. 递归方法
  3. 迭代方式

    两重 while

这里主要提下 递归方法

  1. 正常情况:左节点存在情况下,指向右节点

  1. 特殊情况(跨节点):通过判断当前节点是否有右节点

三、 AC 代码:

public class LeetCode_116 {

    class Node {
        public int val;
        public Node left, right, next;

        public Node(int val) {
            this.val = val;
        }

        public Node(int val, Node left, Node right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    // 方法一:`BFS` 
    // Time: O(n), Space: O(n), Faster: 53.13%
    public Node connectBFS(Node root) {

        if (null == root) return root;

        Queue<Node> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            Node preNode = queue.poll();
            int size = queue.size();

            if (preNode.left != null) queue.add(preNode.left);
            if (preNode.right != null) queue.add(preNode.right);

            while (size > 0) {
                Node node = queue.poll();
                preNode.next = node;
                preNode = node;
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
                --size;
            }
        }
        return root;
    }

    // 方法二:递归方式
    // Time: O(n), Space: O(log(n)), Faster: 100.00%
    public Node connectRecursive(Node root) {
        if (root == null || root.left == null) return root;
        root.left.next = root.right;
        if (root.next != null)
            root.right.next = root.next.left;
        connectRecursive(root.left);
        connectRecursive(root.right);
        return root;
    }

    // 方法三:迭代方式
    // Time: O(n), Space: O(1), Faster: 100.00%
    public Node connectIterative(Node root) {
        if (root == null) return null;
        Node leftMost = root, p;
        while (leftMost.left != null) {
            p = leftMost;
            while (p != null) {
                p.left.next = p.right;
                if (p.next != null)
                    p.right.next = p.next.left;
                p = p.next;
            }
            leftMost = leftMost.left;
        }
        return root;
    }
}

四、总结:

树的遍历模板

树的遍历有四种:

  1. 前序遍历
  2. 中序遍历
  3. 后序遍历
  4. 层级遍历

这里也可以分为: 深度优先遍历( DFS 广度优先遍历 ( BFS

层级遍历:是为广度优先遍历。

其他遍历:是为深度优先遍历。

1. 前序遍历

void traverse(TreeNode root) {
    if (null == root) return;
    
    // 前序遍历的代码
    
    traverse(root.left);
    traverse(root.right);
}

2. 中序遍历

void traverse(TreeNode root) {
    if (null == root) return;
    
    traverse(root.left);
    
    // 前序遍历的代码
    
    traverse(root.right);
}

3. 后序遍历

void traverse(TreeNode root) {
    if (null == root) return;
    
    traverse(root.left);
    traverse(root.right);
    
    // 前序遍历的代码
}

4. 层级遍历

用队列模拟

void traverse(TreeNode root) {
    if (null == root) return;
    
    // 初始化队列,将 root 加入队列
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    
    while (!q.isEmpty()) {
        TreeNode cur = q.poll();
        
        // 层级遍历代码
        System.out.println(root.val);
        
        if (cur.left != null) q.offer(cur.left);
        if (cur.right != null) q.offer(cur.right);
    }
}