LeetCode面试题 17.12 BiNode

02/06 11:46
阅读数 44

LeetCode面试题 17.12 BiNode

一、题目

在这里插入图片描述


二、思路

二叉搜索树特点: 左节点的值不大于父节点的值,右节点的值不小于父节点的值, 因此对二叉搜索树进行中序遍历,可以得到递增的序列。

根据这个思路,可以想到在中序遍历的过程种把每一个子节点的右指针指向父节点,然后把父节点的左指针置空,正如下图所示。

在这里插入图片描述


三、代码实现(Java)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
   
     

    TreeNode head = new TreeNode(-1);
    TreeNode pre = head;

    public TreeNode convertBiNode(TreeNode root) {
   
     
        fun(root);
        return head.right;
    }

    public TreeNode fun(TreeNode root) {
   
     
        if(root == null) return root;
        convertBiNode(root.left);
        pre.right = root;
        pre = root;
        root.left = null;
        convertBiNode(root.right);
        return root;
    }

}

坚持分享,坚持原创,喜欢博主的靓仔靓女们可以看看博主的首页博客!
您的点赞与收藏是我分享博客的最大赞赏!
博主博客地址: https://blog.csdn.net/weixin_43967679

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部