首页 > 代码库 > 二叉树与双向链表问题
二叉树与双向链表问题
做完这道题,我深刻认识到通过边画图边写代码揣摩分析才能真正弄懂这道题,而且如果不是独立思考AC看了题解恐怕就很难弄懂这道题。
这里整理一下题解:本题思路有两种:递归和非递归
Java版AC代码:
数据结构定义:
1 /** 2 public class TreeNode { 3 int val = 0; 4 TreeNode left = null; 5 TreeNode right = null; 6 7 public TreeNode(int val) { 8 this.val = val; 9 10 } 11 } 12 */
递归版:
1 public class Solution { 2 public TreeNode Convert(TreeNode pRootOfTree) { 3 if(pRootOfTree == null) 4 return null; 5 TreeNode res = pRootOfTree; 6 if(pRootOfTree.right != null) { 7 TreeNode tRight = Convert(pRootOfTree.right); 8 pRootOfTree.right = tRight; 9 tRight.left = pRootOfTree; 10 } 11 12 if(pRootOfTree.left != null) { 13 TreeNode tLeft = Convert(pRootOfTree.left); 14 TreeNode tmp = tLeft; 15 while(tmp.right != null) { 16 tmp = tmp.right; 17 } 18 tmp.right = pRootOfTree; 19 pRootOfTree.left = tmp; 20 res = tLeft; 21 } 22 return res; 23 }
非递归版:
Java中有关Stack的API
1 import java.util.Stack; 2 public class Solution {//画图容易理解 3 public TreeNode Convert(TreeNode pRootOfTree) { 4 if(pRootOfTree == null) 5 return null; 6 Stack<TreeNode> st = new Stack<TreeNode>(); 7 TreeNode tnp, tmp = pRootOfTree; 8 TreeNode res = tmp; 9 st.push(tmp); 10 while(tmp.left != null) { 11 tmp = tmp.left; 12 st.push(tmp); 13 } 14 15 if(!st.empty()) 16 res = st.peek(); 17 18 while(!st.empty()) { 19 tmp = st.pop(); 20 tnp = tmp.right; 21 if(tnp != null) { 22 st.push(tnp); 23 while(tnp.left != null) { 24 tnp = tnp.left; 25 st.push(tnp); 26 } 27 tnp.left = tmp; 28 tmp.right = tnp; 29 } else { 30 if(!st.empty()) {//peek()操作前一定要进行判空操作,否则会产生EmptyStack异常 31 tmp.right = st.peek(); 32 tmp.right.left = tmp; 33 } 34 } 35 } 36 return res; 37 } 38 }
C++版AC代码:
数据结构:
1 /* 2 struct TreeNode { 3 int val; 4 struct TreeNode *left; 5 struct TreeNode *right; 6 TreeNode(int x) : 7 val(x), left(NULL), right(NULL) { 8 } 9 };*/
递归版:
1 class Solution { 2 public: 3 TreeNode* Convert(TreeNode* pRootOfTree) 4 { 5 if(pRootOfTree == NULL) 6 return NULL; 7 TreeNode* res = pRootOfTree; 8 TreeNode* tmp = res; 9 if(tmp->right != NULL) { 10 TreeNode* tRight = Convert(tmp->right); 11 pRootOfTree->right = tRight; 12 tRight->left = pRootOfTree; 13 } 14 15 if(tmp->left != NULL) { 16 TreeNode* tLeft = Convert(tmp->left); 17 res = tLeft; 18 while(tLeft->right != NULL) { 19 tLeft = tLeft->right; 20 } 21 tLeft->right = pRootOfTree; 22 pRootOfTree->left = tLeft; 23 } 24 25 return res; 26 } 27 };
非递归版:
C++关于stack(首字母小写)的API
- bool empty();//判空
- void pop();//出栈
- void push(const Type &val);//入栈
- size_type size();//得到栈的大小
- Type &top();//取得栈顶元素引用但不弹出
1 #include <bits/stdc++.h> 2 class Solution { 3 public: 4 TreeNode* Convert(TreeNode* pRootOfTree) 5 { 6 if(pRootOfTree == NULL) 7 return NULL; 8 stack<TreeNode*> st; 9 st.push(pRootOfTree); 10 TreeNode* tmp = pRootOfTree; 11 TreeNode* tnp, *res = tmp; 12 while(tmp->left != NULL) { 13 tmp = tmp->left; 14 st.push(tmp); 15 } 16 17 if(!st.empty()) { 18 res = st.top(); 19 } 20 21 while(!st.empty()) { 22 tmp = st.top(); 23 st.pop(); 24 tnp = tmp->right; 25 if(tnp != NULL) { 26 st.push(tnp); 27 while(tnp->left != NULL) { 28 tnp = tnp->left; 29 st.push(tnp); 30 } 31 tnp->left = tmp; 32 tmp->right = tnp; 33 } else { 34 if(!st.empty()) {//一定注意要判空 35 tmp->right = st.top(); 36 tmp->right->left = tmp; 37 } 38 } 39 } 40 return res; 41 } 42 };
二叉树与双向链表问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。