首页 > 代码库 > Leetcode:Flatten Binary Tree to Linked List 解题报告
Leetcode:Flatten Binary Tree to Linked List 解题报告
Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place.
For example,
Given
1 / 2 5 / \ 3 4 6
The flattened tree should look like:
1 2 3 4 5 6
SOLUTION 1:
使用递归解决，根据left是否为空，先连接left tree, 然后再连接右子树。使用一个tail 来记录链的结尾。在递归之前，先将root.left,root.right保存下来。
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */10 public class Solution {11 public void flatten(TreeNode root) {12 dfs(root);13 }14 15 // return : the tail of the list.16 public TreeNode dfs(TreeNode root) {17 if (root == null) {18 return null;19 }20 21 TreeNode left = root.left;22 TreeNode right = root.right;23 24 // Init the root. 25 root.left = null;26 root.right = null;27 28 TreeNode tail = root;29 30 // connect the left tree.31 if (left != null) {32 tail.right = left;33 tail = dfs(left);34 }35 36 // connect the right tree.37 if (right != null) {38 tail.right = right;39 tail = dfs(right);40 }41 42 return tail;43 }44 }
Leetcode:Flatten Binary Tree to Linked List 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。