欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-20 20:23:36
...

传送门

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

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

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

方法1. 递归常数空间

	public Node connect(Node root) { 
        if (root == null) return null;
        Node leftNode = root.left, rightNode = root.right;
        // 把二叉树劈成两半, 在while循环里完成连接工作
        while (leftNode != null) { 
            leftNode.next = rightNode;
            leftNode = leftNode.right; //左节点的右儿子 连接上 右节点的左儿子 
            rightNode = rightNode.left;//根据完全二叉树的特性,不用rightNode判空
        }
        connect(root.left);
        connect(root.right);
        return root;
   }

方法2. 队列层次遍历 非常数空间

	public Node connect(Node root) {
        Queue<Node> que = new LinkedList<Node>();
        if(root == null) return null;
        que.offer(root);
        int curCount, nextCount = 1;
        while (que.size() != 0) {
            Node rightNode = null; 
            curCount = nextCount;
            nextCount = 0;
            while (que.size() != 0 && curCount-- > 0) {
                Node leftNode = que.poll(); // 左节点出队,
                leftNode.next = rightNode; // 左节点next指向右边节点
                rightNode = leftNode; // 右边节点更新为当前左节点(横向 平行向左移动)
                if (leftNode.right != null) { // 从 右往左 入队列
                    que.offer(leftNode.right);
                    nextCount++;
                } 
                if (leftNode.left != null) {
                    que.offer(leftNode.left);
                    nextCount++;
                } 
            }
        }
        return root;
	}