LeetCode面試題 17.12 BiNode
- 一、題目
- 二、思路
- 三、代碼實作(Java)
一、題目
二、思路
二叉搜索樹特點: 左節點的值不大于父節點的值,右節點的值不小于父節點的值, 因此對二叉搜索樹進行中序遍歷，可以得到遞增的序列，
根據這個思路，可以想到在中序遍歷的程序種把每一個子節點的右指標指向父節點，然后把父節點的左指標置空，正如下圖所示，
三、代碼實作(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
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/256703.html
標籤：其他