美文网首页
【D5】二叉树的中序遍历 & 二叉树展开为链表 & 填充每个节点

【D5】二叉树的中序遍历 & 二叉树展开为链表 & 填充每个节点

作者: sirenyunpan | 来源:发表于2021-02-04 21:21 被阅读0次

94. 二叉树的中序遍历

问题描述

给定一个二叉树的根节点 root ,返回它的 中序 遍历。

代码实现1-递归法

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
       List<Integer> res = new ArrayList<Integer>();
       inorder(root,res);
       return res;
    }

    public void inorder(TreeNode root, List<Integer> res){
        if(root == null){
            return;
        }
        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);
    }   
}

代码实现2-迭代法

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
       List<Integer> res = new ArrayList<Integer>();

       Deque<TreeNode> stack = new LinkedList<>();
       while(root != null || !stack.isEmpty()){  
           while(root != null){
               //左子树入栈
               stack.offerLast(root);
               root = root.left;
           }
           //节点出栈
           root = stack.removeLast();
           res.add(root.val);
           root = root.right;
       }
       return res;
    }   
}

114. 二叉树展开为链表

问题描述

给你二叉树的根结点 root ,请你将它展开为一个单链表:

  • 展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。
  • 展开后的单链表应该与二叉树 先序遍历 顺序相同。

解题思路

先获取先序遍历的结果,然后根据先序遍历的结果修改二叉树的原有结构

代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        //用队列存储先序遍历的结果
        Queue<TreeNode> preOrder = new LinkedList<>();
        
        //1.得到先序遍历的结果
        Deque<TreeNode> stack = new LinkedList<>();
        while(root != null || !stack.isEmpty()){
           while(root != null){
               preOrder.add(root);
               stack.offerLast(root);
               root = root.left;
           }
           root = stack.removeLast();
           root = root.right;
        }
        
        if(preOrder.size() > 1){
            //2.如果节点数大于1,构建新的左右子树
            root = preOrder.remove();
            while(!preOrder.isEmpty()){
                root.left = null;
                root.right = preOrder.remove();
                root = root.right;
            }
        }
    
    }
}

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

问题描述

给定一个 完美二叉树 ,其所有叶子节点都在同一层,每个父节点都有两个子节点。填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。初始状态下,所有 next 指针都被设置为 NULL。

解题思路

需要连接的节点有两类。一类是同一父节点的左右节点;另一类是在同一层的相邻父节点的右子节点 与左子节点。

代码实现

/*
// 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){
            //连接同一父节点的左右节点。示例图中的2->3
            root.left.next = root.right;
            if(root.next != null){
                 //连接不同父节点的右左节点。示例图中5->6
                 root.right.next = root.next.left;
            }
        } 
        connect(root.left);
        connect(root.right);
        return root;   
    }
}

相关文章

  • 链表和二叉树

    单向链表 链表反转 二叉树定义 1、递归中序遍历 2、迭代中序遍历 3、二叉树层序遍历 4、判断一棵树是否为平衡树...

  • java 二叉树遍历算法

    二叉树的遍历可以分为先序、中序、后序、层次遍历。 前序遍历,遍历节点的顺序为:根—>左—>右;中序遍历,遍历节点的...

  • 二叉树操作

    树节点 逐行顺序解析二叉树 前序遍历二叉树 中序遍历二叉树 后序遍历二叉树 删除指定数值的节点 前序遍历顺序存储的...

  • 数据结构复习(JavaScript)

    一、二叉树 1.1 二叉树遍历 中序遍历、前序遍历、后序遍历(根据根节点遍历次序划分)中序遍历: 1.2 重建二叉...

  • 114. Flatten Binary Tree to Link

    题目 给定一个二叉树的根 root,将这棵二叉树展开为链表。这个链表有两个特性 链表节点由二叉树类表示,节点左节点...

  • 数据结构(六)-二叉树

    二叉树的特点是每个节点最多有两个分支,即二叉树中不存在度大于2的结点。 二叉树的遍历 先序遍历(根-左-右) 中序...

  • 二叉树转链表

    给定一个二叉树,将该二叉树 就地(in-place)转换为单链表。单链表中节点顺序 为二叉树前序遍历顺序。(不额外...

  • 二叉树

    1.二叉树的遍历:前序、中序、后序遍历 2.二叉树查找节点和删除节点的代码

  • LeetCode94 二叉树的中序遍历

    题目 二叉树的中序遍历 题目描述 给出一个二叉树 用中序遍历输出 方案 中序遍历:考察到一个节点后,将其暂存,遍历...

  • 二叉树

    1、二叉树的遍历(递归思想) 中序遍历: 【左子树,节点,右子树】后序遍历: 【左子树,右子树,节点】中序遍历: ...

网友评论

      本文标题:【D5】二叉树的中序遍历 & 二叉树展开为链表 & 填充每个节点

      本文链接:https://www.haomeiwen.com/subject/nhibtltx.html