文章目錄

• 題目描述
• 思路 && 代碼
• • • 1. 非原地算法
    • 2. 原地算法
    • 二刷

題目描述

• 談到二叉搜索樹，那就得考慮考慮中序遍歷啦～
• 這道題對中序遍歷的理解提升很有好處！
  
  

思路 && 代碼

1. 非原地算法

• 最簡單的做法，依賴ArrayList，但是不滿足原地算法的要求
• 只要通過中序遍歷，把樹上結(jié)點存儲到ArrayList中，再通過下標(biāo)進(jìn)行操作即可。

/* // Definition for a Node. class Node {public int val;public Node left;public Node right;public Node() {}public Node(int _val) {val = _val;}public Node(int _val,Node _left,Node _right) {val = _val;left = _left;right = _right;} }; */ class Solution {ArrayList<Node> list = new ArrayList<>();public Node treeToDoublyList(Node root) {if(root == null) {return null;}// 先中序遍歷存儲結(jié)點midErgodic(root);// 接著逐個改變指針for(int i = 0; i < list.size(); i++) {if(i == 0) {list.get(i).left = list.get(list.size() - 1);}else {list.get(i).left = list.get(i - 1);}if(i == list.size() - 1) {list.get(i).right = list.get(0);}else {list.get(i).right = list.get(i + 1);}}return list.get(0);}public void midErgodic(Node root) {if(root == null) {return;}midErgodic(root.left);list.add(root);midErgodic(root.right);} }

2. 原地算法

• 和1異曲同工，但是相對更加巧妙！
• Node first：存儲最左邊的**“首位”**結(jié)點，用于最后的處理
• Node pre：在遞歸中輔助使用，遞歸結(jié)束后指向**“末尾”**結(jié)點
• 同樣是中序遍歷，要注意好 cur 、pre 的處理
• cur 是局部變量；pre、first 是全局變量

// 很經(jīng)典的中序遍歷題～ class Solution {Node first, pre;public Node treeToDoublyList(Node root) {// 空樹情況if(root == null) {return null;}// 開啟dfsdfs(root);// dfs結(jié)束，此時 pre 就是最右邊（最大）節(jié)點.// 進(jìn)行頭 - 尾節(jié)點的處理first.left = pre;pre.right = first;return first;}public void dfs(Node cur) {if(cur == null) {return;}// 中序dfs(cur.left);// right 的處理，沒有 pre 節(jié)點的是 firstif(pre != null) {pre.right = cur;}else {first = cur;}// left 的處理cur.left = pre;// 維護(hù) pre 結(jié)點pre = cur;dfs(cur.right);} }

二刷

• 中序遍歷 + 全局變量

class Solution {Node head = null;Node pre = null;public Node treeToDoublyList(Node root) {if(root == null) {return null;}dfs(root);head.left = pre;pre.right = head;return head;}public void dfs(Node root) {if(root == null) {return;}treeToDoublyList(root.left);if(pre == null) {head = root;}else {pre.right = root;}root.left = pre;pre = root;treeToDoublyList(root.right);} }

總結(jié)

以上是生活随笔為你收集整理的【LeetCode笔记】剑指 Offer 36. 二叉搜索树与双向链表（Java、二叉树、链表、原地算法）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。