226. 翻轉(zhuǎn)二叉樹
翻轉(zhuǎn)一棵二叉樹。
解題思路及方法
這道題很簡單坷随，可以作為剛刷二叉樹的基礎(chǔ)題房铭，解法就是普通的遞歸驻龟。交換根節(jié)點的左右子結(jié)點温眉，然后一直遞歸調(diào)用直到遍歷完整棵樹。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
// 交換左右節(jié)點
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
// 遞歸交換子節(jié)點
invertTree(root.left);
invertTree(root.right);
return root;
}
}
結(jié)果如下：
116. 填充每個節(jié)點的下一個右側(cè)節(jié)點指針
給定一個 完美二叉樹 翁狐，其所有葉子節(jié)點都在同一層类溢，每個父節(jié)點都有兩個子節(jié)點。二叉樹定義如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每個 next 指針露懒，讓這個指針指向其下一個右側(cè)節(jié)點闯冷。如果找不到下一個右側(cè)節(jié)點，則將 next 指針設(shè)置為 NULL懈词。
初始狀態(tài)下蛇耀，所有 next 指針都被設(shè)置為 NULL。
進(jìn)階：
你只能使用常量級額外空間坎弯。
使用遞歸解題也符合要求纺涤，本題中遞歸程序占用的椧朐荩空間不算做額外的空間復(fù)雜度。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有撩炊。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)外永，非商業(yè)轉(zhuǎn)載請注明出處。
解題方法及思路
首先我們要清楚什么是一棵完美二叉樹拧咳，完美二叉樹就是一棵滿的二叉樹伯顶，也就是非葉結(jié)點都有兩個子結(jié)點，即都是二叉的骆膝。搞清楚定義就好解了祭衩。
觀察示例，其實就是將子結(jié)點的右子結(jié)點接在左子結(jié)點的后面谭网。這么想是對的汪厨，但是不全對，觀察結(jié)點5和6愉择，它們并非一個結(jié)點的左右子結(jié)點劫乱，所以還要考慮這種情況。
編寫一個輔助函數(shù)來鏈接子結(jié)點锥涕，參數(shù)為兩個結(jié)點衷戈。將傳入的兩個結(jié)點的左右子結(jié)點鏈接，再將第一個結(jié)點的右子結(jié)點和第二個結(jié)點的左子結(jié)點鏈接层坠，一直遞歸即可殖妇。
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/
class Solution {
public Node connect(Node root) {
if (root == null) {
return null;
}
// 鏈接
connectTwoNode(root.left, root.right);
return root;
}
public void connectTwoNode(Node node1, Node node2) {
if (node1 == null || node2 == null) {
return;
}
// 鏈接傳入根節(jié)點
node1.next = node2;
// 鏈接傳入結(jié)點子節(jié)點
connectTwoNode(node1.left, node1.right);
connectTwoNode(node2.left, node2.right);
// 鏈接傳入結(jié)點右子樹和左子樹
connectTwoNode(node1.right, node2.left);
}
}
結(jié)果如下：
114. 二叉樹展開為鏈表
給你二叉樹的根結(jié)點 root ，請你將它展開為一個單鏈表：
展開后的單鏈表應(yīng)該同樣使用 TreeNode 破花，其中 right 子指針指向鏈表中下一個結(jié)點谦趣，而左子指針始終為 null 。
展開后的單鏈表應(yīng)該與二叉樹 先序遍歷 順序相同座每。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有前鹅。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處峭梳。
解題思路及方法
同樣是遞歸舰绘，將子結(jié)點拉成鏈表。因為要求是先序遍歷的順序葱椭，所以遞歸函數(shù)的寫法是先遞歸捂寿，再處理。處理過程是將當(dāng)前結(jié)點的左右子樹存入一個臨時變量，然后將左子樹為空，將之前存入變量的左子樹賦給當(dāng)前右子樹滋早，再將之前存入右子樹的變量接在現(xiàn)在右子樹的右邊，形成一個鏈表驳概。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public void flatten(TreeNode root) {
if (root == null) {
return;
}
// 遞歸將子結(jié)點拉成鏈表
flatten(root.left);
flatten(root.right);
// 將傳入結(jié)點與子結(jié)點拉成鏈表
TreeNode left = root.left;
TreeNode right = root.right;
root.left = null;
root.right = left;
// 將原先的右子樹接到當(dāng)前右子樹的末端
TreeNode p = root;
while (p.right != null) {
p = p.right;
}
p.right = right;
}
}
結(jié)果如下：
