二叉树与双向链表

发表于 | 分类于 | 浏览 次

将二叉树转成双向链表。

将二叉搜索树转成双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。二叉树与双向链表

递归方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        TreeNode* lastNode = nullptr;
        ConvertCore(pRootOfTree, lastNode);
        while(lastNode && lastNode->left)
            lastNode = lastNode->left;
        return lastNode;
    }
    void ConvertCore(TreeNode* node, TreeNode* &lastNode){
        // lastNode表示双向链表中最后一个节点,node表示当前的根节点
        // 首先考虑node的左子树，若左子树不空，则先转换左子树，并且lastNode表示左子树转换成的双向链表中
        // 的最后一个节点，那么指向让node->left = lastNode,若lastNode不为空，令lastNode->right=node
        // 返回
        if(node == nullptr){
            return;
        }
        if(node->left){
            ConvertCore(node->left, lastNode);
        }
        node->left = lastNode;
        if(lastNode!=nullptr){
            lastNode->right = node;
        }
        lastNode = node;
        if(node->right!=nullptr){
            ConvertCore(node->right, lastNode);
        }
    }
};

非递归解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if(pRootOfTree==nullptr){
            return nullptr;
        }
        ConvertCore(pRootOfTree);
        return pRootOfTree;
    }
     
    void ConvertCore(TreeNode* &root){
        stack<TreeNode*> st;
        TreeNode* cur = nullptr;
        TreeNode* node = root;
        while(node!=nullptr || !st.empty()){
            if(node==nullptr){
                node = st.top();
                st.pop();
                if(cur != nullptr){
                    cur->right = node;
                }else{
                    root = node;
                }
                node->left = cur;
                cur = node;
                node = node->right;
                 
            }else{
                st.push(node);
                node = node->left;
            }
        }
    }
};

114. Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:

1
2
3
4
5
    1
   / \
  2   5
 / \   \
3   4   6

The flattened tree should look like:

1
2
3
4
5
6
7
8
9
10
11
1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

参考“参考文献1”，有多种解法。

430. Flatten a Multilevel Doubly Linked List

参考文献

[1]Flatten Binary Tree to Linked List：https://www.cnblogs.com/grandyang/p/4293853.html