东哥带你刷二叉树(思路篇)

读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:

LeetCode 力扣 难度
114. Flatten Binary Tree to Linked List 114. 二叉树展开为链表 🟠
116. Populating Next Right Pointers in Each Node 116. 填充每个节点的下一个右侧节点指针 🟠
226. Invert Binary Tree 226. 翻转二叉树 🟢
- 剑指 Offer 27. 二叉树的镜像 🟢

———–

本文有视频版: 二叉树/递归的框架思维(纲领篇)。建议关注我的 B 站账号,我会用视频领读的方式带大家学习那些稍有难度的算法技巧。

在开头先打个广告,我的 手把手刷二叉树课程 按照公式和套路讲解了 150 道二叉树题目,只需一顿饭钱,就能手把手带你刷完二叉树分类的题目,迅速掌握递归思维,让你豁然开朗。我绝对有这个信心,信不信,可以等你看完我的二叉树算法系列文章再做评判。

本文承接 东哥带你刷二叉树(纲领篇),先复述一下前文总结的二叉树解题总纲:

二叉树解题的思维模式分两类:

1、是否可以通过遍历一遍二叉树得到答案?如果可以,用一个 traverse 函数配合外部变量来实现,这叫「遍历」的思维模式。

2、是否可以定义一个递归函数,通过子问题(子树)的答案推导出原问题的答案?如果可以,写出这个递归函数的定义,并充分利用这个函数的返回值,这叫「分解问题」的思维模式。

无论使用哪种思维模式,你都需要思考:

如果单独抽出一个二叉树节点,它需要做什么事情?需要在什么时候(前/中/后序位置)做?其他的节点不用你操心,递归函数会帮你在所有节点上执行相同的操作。

本文就以几道比较简单的题目为例,带你实践运用这几条总纲,理解「遍历」的思维和「分解问题」的思维有何区别和联系。

一、翻转二叉树

我们先从简单的题开始,看看力扣第 226 题「 翻转二叉树」,输入一个二叉树根节点 root,让你把整棵树镜像翻转,比如输入的二叉树如下:

     4
   /   \
  2     7
 / \   / \
1   3 6   9

算法原地翻转二叉树,使得以 root 为根的树变成:

     4
   /   \
  7     2
 / \   / \
9   6 3   1

不难发现,只要把二叉树上的每一个节点的左右子节点进行交换,最后的结果就是完全翻转之后的二叉树。

那么现在开始在心中默念二叉树解题总纲:

1、这题能不能用「遍历」的思维模式解决

可以,我写一个 traverse 函数遍历每个节点,让每个节点的左右子节点颠倒过来就行了。

单独抽出一个节点,需要让它做什么?让它把自己的左右子节点交换一下。

需要在什么时候做?好像前中后序位置都可以。

综上,可以写出如下解法代码:

// 主函数
TreeNode invertTree(TreeNode root) {
    // 遍历二叉树,交换每个节点的子节点
    traverse(root);
    return root;
}

// 二叉树遍历函数
void traverse(TreeNode root) {
    if (root == null) {
        return;
    }

    /**** 前序位置 ****/
    // 每一个节点需要做的事就是交换它的左右子节点
    TreeNode tmp = root.left;
    root.left = root.right;
    root.right = tmp;

    // 遍历框架,去遍历左右子树的节点
    traverse(root.left);
    traverse(root.right);
}
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

// 主函数
TreeNode* invertTree(TreeNode* root) {
    // 遍历二叉树,交换每个节点的子节点
    traverse(root);
    return root;
}

// 二叉树遍历函数
void traverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }

    /**** 前序位置 ****/
    // 每一个节点需要做的事就是交换它的左右子节点
    TreeNode* tmp = root->left;
    root->left = root->right;
    root->right = tmp;

    // 遍历框架,去遍历左右子树的节点
    traverse(root->left);
    traverse(root->right);
}
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

# 主函数
def invertTree(root: TreeNode) -> TreeNode:
    # 遍历二叉树,交换每个节点的子节点
    traverse(root)
    return root

# 二叉树遍历函数
def traverse(root: TreeNode):
    if not root:
        return

    /**** 前序位置 ****/
    # 每一个节点需要做的事就是交换它的左右子节点
    tmp = root.left
    root.left = root.right
    root.right = tmp

    # 遍历框架,去遍历左右子树的节点
    traverse(root.left)
    traverse(root.right)
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

// 主函数
func invertTree(root *TreeNode) *TreeNode {
    // 遍历二叉树,交换每个节点的子节点
    traverse(root)
    return root
}

// 二叉树遍历函数
func traverse(root *TreeNode) {
    if root == nil {
        return
    }

    /**** 前序位置 ****/
    // 每一个节点需要做的事就是交换它的左右子节点
    tmp := root.Left
    root.Left = root.Right
    root.Right = tmp

    // 遍历框架,去遍历左右子树的节点
    traverse(root.Left)
    traverse(root.Right)
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

var invertTree = function(root) {
    const traverse = function(root) {
        if (root === null) {
            return;
        }

        /**** 前序位置 ****/
        // 每一个节点需要做的事就是交换它的左右子节点
        let tmp = root.left;
        root.left = root.right;
        root.right = tmp;

        // 遍历框架,去遍历左右子树的节点
        traverse(root.left);
        traverse(root.right);
    };
    
    // 遍历二叉树,交换每个节点的子节点
    traverse(root);
    return root;
};

🍭 代码可视化动画 🍭

你把前序位置的代码移到后序位置也可以,但是直接移到中序位置是不行的,需要稍作修改,这应该很容易看出来吧,我就不说了。

按理说,这道题已经解决了,不过为了对比,我们再继续思考下去。

2、这题能不能用「分解问题」的思维模式解决

我们尝试给 invertTree 函数赋予一个定义:

// 定义:将以 root 为根的这棵二叉树翻转,返回翻转后的二叉树的根节点
TreeNode invertTree(TreeNode root);
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

// 定义:将以 root 为根的这棵二叉树翻转,返回翻转后的二叉树的根节点
TreeNode* invertTree(TreeNode* root);
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

# 定义:将以 root 为根的这棵二叉树翻转,返回翻转后的二叉树的根节点
def invertTree(root: TreeNode) -> TreeNode:
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

// 定义:将以 root 为根的这棵二叉树翻转,返回翻转后的二叉树的根节点
func invertTree(root *TreeNode) *TreeNode
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

// 定义:将以 root 为根的这棵二叉树翻转,返回翻转后的二叉树的根节点
var invertTree = function(root) {
    // 函数体
};

然后思考,对于某一个二叉树节点 x 执行 invertTree(x),你能利用这个递归函数的定义做点啥?

我可以用 invertTree(x.left) 先把 x 的左子树翻转,再用 invertTree(x.right)x 的右子树翻转,最后把 x 的左右子树交换,这恰好完成了以 x 为根的整棵二叉树的翻转,即完成了 invertTree(x) 的定义。

直接写出解法代码:

// 定义:将以 root 为根的这棵二叉树翻转,返回翻转后的二叉树的根节点
TreeNode invertTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    // 利用函数定义,先翻转左右子树
    TreeNode left = invertTree(root.left);
    TreeNode right = invertTree(root.right);

    // 然后交换左右子节点
    root.left = right;
    root.right = left;

    // 和定义逻辑自恰:以 root 为根的这棵二叉树已经被翻转,返回 root
    return root;
}
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

// 定义:将以 root 为根的这棵二叉树翻转,返回翻转后的二叉树的根节点
TreeNode* invertTree(TreeNode* root) {
    if (root == nullptr) {
        return nullptr;
    }
    // 利用函数定义,先翻转左右子树
    TreeNode* left = invertTree(root->left);
    TreeNode* right = invertTree(root->right);

    // 然后交换左右子节点
    root->left = right;
    root->right = left;

    // 和定义逻辑自恰:以 root 为根的这棵二叉树已经被翻转,返回 root
    return root;
}
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

# 定义:将以 root 为根的这棵二叉树翻转,返回翻转后的二叉树的根节点
def invertTree(root: TreeNode) -> TreeNode:
    if root is None:
        return None
    
    # 利用函数定义,先翻转左右子树
    left = invertTree(root.left)
    right = invertTree(root.right)

    # 然后交换左右子节点
    root.left = right
    root.right = left

    # 和定义逻辑自恰:以 root 为根的这棵二叉树已经被翻转,返回 root
    return root
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

// 定义:将以 root 为根的这棵二叉树翻转,返回翻转后的二叉树的根节点
func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    // 利用函数定义,先翻转左右子树
    left := invertTree(root.left)
    right := invertTree(root.right)

    // 然后交换左右子节点
    root.left = right
    root.right = left

    // 和定义逻辑自恰:以 root 为根的这棵二叉树已经被翻转,返回 root
    return root
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

// 定义:将以 root 为根的这棵二叉树翻转,返回翻转后的二叉树的根节点
var invertTree = function(root) {
    if (root === null) {
        return null;
    }
    // 利用函数定义,先翻转左右子树
    var left = invertTree(root.left);
    var right = invertTree(root.right);

    // 然后交换左右子节点
    root.left = right;
    root.right = left;

    // 和定义逻辑自恰:以 root 为根的这棵二叉树已经被翻转,返回 root
    return root;
}

这种「分解问题」的思路,核心在于你要给递归函数一个合适的定义,然后用函数的定义来解释你的代码;如果你的逻辑成功自恰,那么说明你这个算法是正确的。

好了,这道题就分析到这,「遍历」和「分解问题」的思路都可以解决,看下一道题。

第二题、填充节点的右侧指针

这是力扣第 116 题「 填充每个二叉树节点的右侧指针」,看下题目:

函数签名如下:

Node connect(Node root);
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

Node* connect(Node* root);
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

def connect(root: Node) -> Node:
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

func connect(root *Node) *Node
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

var connect = function(root) {};

题目的意思就是把二叉树的每一层节点都用 next 指针连接起来:

而且题目说了,输入是一棵「完美二叉树」,形象地说整棵二叉树是一个正三角形,除了最右侧的节点 next 指针会指向 null,其他节点的右侧一定有相邻的节点。

这道题怎么做呢?来默念二叉树解题总纲:

1、这题能不能用「遍历」的思维模式解决

很显然,一定可以。

每个节点要做的事也很简单,把自己的 next 指针指向右侧节点就行了。

也许你会模仿上一道题,直接写出如下代码:

// 二叉树遍历函数
void traverse(Node root) {
    if (root == null || root.left == null) {
        return;
    }
    // 把左子节点的 next 指针指向右子节点
    root.left.next = root.right;

    traverse(root.left);
    traverse(root.right);
}
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

// 二叉树遍历函数
void traverse(Node* root) {
    if (root == nullptr || root->left == nullptr) {
        return;
    }
    // 把左子节点的 next 指针指向右子节点
    root->left->next = root->right;

    traverse(root->left);
    traverse(root->right);
}
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

# 二叉树遍历函数
def traverse(root: Node) -> None:
    if not root or not root.left:
        return
    # 把左子节点的 next 指针指向右子节点
    root.left.next = root.right
    
    traverse(root.left)
    traverse(root.right)
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

// 二叉树遍历函数
func traverse(root *Node) {
	if root == nil || root.left == nil {
		return
	}
	// 把左子节点的 next 指针指向右子节点
	root.left.next = root.right

	traverse(root.left)
	traverse(root.right)
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

// 二叉树遍历函数
function traverse(root) {
    if (root == null || root.left == null) {
        return;
    }
    // 把左子节点的 next 指针指向右子节点
    root.left.next = root.right;

    traverse(root.left);
    traverse(root.right);
}

但是,这段代码其实有很大问题,因为它只能把相同父节点的两个节点穿起来,再看看这张图:

节点 5 和节点 6 不属于同一个父节点,那么按照这段代码的逻辑,它俩就没办法被穿起来,这是不符合题意的,但是问题出在哪里?

传统的 traverse 函数是遍历二叉树的所有节点,但现在我们想遍历的其实是两个相邻节点之间的「空隙」

所以我们可以在二叉树的基础上进行抽象,你把图中的每一个方框看做一个节点:

这样,一棵二叉树被抽象成了一棵三叉树,三叉树上的每个节点就是原先二叉树的两个相邻节点

现在,我们只要实现一个 traverse 函数来遍历这棵三叉树,每个「三叉树节点」需要做的事就是把自己内部的两个二叉树节点穿起来:

// 主函数
Node connect(Node root) {
    if (root == null) return null;
    // 遍历「三叉树」,连接相邻节点
    traverse(root.left, root.right);
    return root;
}

// 三叉树遍历框架
void traverse(Node node1, Node node2) {
    if (node1 == null || node2 == null) {
        return;
    }
    /**** 前序位置 ****/
    // 将传入的两个节点穿起来
    node1.next = node2;
    
    // 连接相同父节点的两个子节点
    traverse(node1.left, node1.right);
    traverse(node2.left, node2.right);
    // 连接跨越父节点的两个子节点
    traverse(node1.right, node2.left);
}
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

// 主函数
Node* connect(Node* root) {
    if (root == nullptr) return nullptr;
    // 遍历「三叉树」,连接相邻节点
    traverse(root->left, root->right);
    return root;
}

// 三叉树遍历框架
void traverse(Node* node1, Node* node2) {
    if (node1 == nullptr || node2 == nullptr) {
        return;
    }
    /**** 前序位置 ****/
    // 将传入的两个节点穿起来
    node1->next = node2;
    
    // 连接相同父节点的两个子节点
    traverse(node1->left, node1->right);
    traverse(node2->left, node2->right);
    // 连接跨越父节点的两个子节点
    traverse(node1->right, node2->left);
}
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

# 主函数
def connect(root: 'Node') -> 'Node':
    if root is None:
        return None
    # 遍历「三叉树」,连接相邻节点
    traverse(root.left, root.right)
    return root

# 三叉树遍历框架
def traverse(node1: 'Node', node2: 'Node'):
    if node1 is None or node2 is None:
        return
    /**** 前序位置 ****/
    # 将传入的两个节点穿起来
    node1.next = node2

    # 连接相同父节点的两个子节点
    traverse(node1.left, node1.right)
    traverse(node2.left, node2.right)
    # 连接跨越父节点的两个子节点
    traverse(node1.right, node2.left)
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

// Node结构体
type Node struct {
    Val int
    Left, Right, Next *Node
}

func connect(root *Node) *Node {
    if root == nil {
        return nil
    }
    // 遍历「三叉树」,连接相邻节点
    traverse(root.Left, root.Right)
    return root
}

// 三叉树遍历框架
func traverse(node1, node2 *Node) {
    if node1 == nil || node2 == nil {
        return
    }
    /**** 前序位置 ****/
    // 将传入的两个节点穿起来
    node1.Next = node2
    
    // 连接相同父节点的两个子节点
    traverse(node1.Left, node1.Right)
    traverse(node2.Left, node2.Right)
    // 连接跨越父节点的两个子节点
    traverse(node1.Right, node2.Left)
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

// 主函数
var connect = function(root) {
    if (root === null) return null;
    // 遍历「三叉树」,连接相邻节点
    traverse(root.left, root.right);
    return root;
}

// 三叉树遍历框架
function traverse(node1, node2) {
    if (node1 === null || node2 === null) {
        return;
    }
    /**** 前序位置 ****/
    // 将传入的两个节点穿起来
    node1.next = node2;
    
    // 连接相同父节点的两个子节点
    traverse(node1.left, node1.right);
    traverse(node2.left, node2.right);
    // 连接跨越父节点的两个子节点
    traverse(node1.right, node2.left);
}

这样,traverse 函数遍历整棵「三叉树」,将所有相邻节的二叉树节点都连接起来,也就避免了我们之前出现的问题,把这道题完美解决。

2、这题能不能用「分解问题」的思维模式解决

嗯,好像没有什么特别好的思路,所以这道题无法使用「分解问题」的思维来解决。

第三题、将二叉树展开为链表

这是力扣第 114 题「 将二叉树展开为链表」,看下题目:

函数签名如下:

void flatten(TreeNode root);
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

void flatten(TreeNode* root);
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

def flatten(root):
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

func flatten(root *TreeNode)
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

var flatten = function(root) {
    // function code here
};

1、这题能不能用「遍历」的思维模式解决

乍一看感觉是可以的:对整棵树进行前序遍历,一边遍历一边构造出一条「链表」就行了:

// 虚拟头节点,dummy.right 就是结果
TreeNode dummy = new TreeNode(-1);
// 用来构建链表的指针
TreeNode p = dummy;

void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    // 前序位置
    p.right = new TreeNode(root.val);
    p = p.right;

    traverse(root.left);
    traverse(root.right);
}
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

// 虚拟头节点,dummy.right 就是结果
TreeNode* dummy = new TreeNode(-1);
    // 用来构建链表的指针
    TreeNode* p = dummy;

void traverse(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    // 前序位置
    p->right = new TreeNode(root->val);
    p = p->right;

    traverse(root->left);
    traverse(root->right);
}
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

# 虚拟头节点,dummy.right 就是结果
dummy = TreeNode(-1)
# 用来构建链表的指针
p = dummy

def traverse(root: TreeNode) -> None:
    if not root:
        return
    # 前序位置
    p.right = TreeNode(root.val)
    p = p.right

    traverse(root.left)
    traverse(root.right)
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

// 虚拟头节点,dummy.right 就是结果
dummy := &TreeNode{-1, nil, nil}
// 用来构建链表的指针
p := dummy

func traverse(root *TreeNode) {
    if root == nil {
        return
    }
    // 前序位置
    p.Right = &TreeNode{root.Val, nil, nil}
    p = p.Right

    traverse(root.Left)
    traverse(root.Right)
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

// 虚拟头节点,dummy.right 就是结果
var dummy = new TreeNode(-1);
// 用来构建链表的指针
var p = dummy;

function traverse(root) {
    if (root == null) {
        return;
    }
    // 前序位置
    p.right = new TreeNode(root.val);
    p = p.right;

    traverse(root.left);
    traverse(root.right);
}

但是注意 flatten 函数的签名,返回类型为 void,也就是说题目希望我们在原地把二叉树拉平成链表。

这样一来,没办法通过简单的二叉树遍历来解决这道题了。

2、这题能不能用「分解问题」的思维模式解决

我们尝试给出 flatten 函数的定义:

// 定义:输入节点 root,然后 root 为根的二叉树就会被拉平为一条链表
void flatten(TreeNode root);
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

// 定义:输入节点 root,然后 root 为根的二叉树就会被拉平为一条链表
void flatten(TreeNode* root);
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

# 定义:输入节点 root,然后 root 为根的二叉树就会被拉平为一条链表
def flatten(root: TreeNode):
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

// 定义:输入节点 root,然后 root 为根的二叉树就会被拉平为一条链表
func flatten(root *TreeNode) {    
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

// 定义:输入节点 root,然后 root 为根的二叉树就会被拉平为一条链表
var flatten = function(root) {};

有了这个函数定义,如何按题目要求把一棵树拉平成一条链表?

对于一个节点 x,可以执行以下流程:

1、先利用 flatten(x.left)flatten(x.right)x 的左右子树拉平。

2、将 x 的右子树接到左子树下方,然后将整个左子树作为右子树。

这样,以 x 为根的整棵二叉树就被拉平了,恰好完成了 flatten(x) 的定义。

直接看代码实现:

// 定义:将以 root 为根的树拉平为链表
void flatten(TreeNode root) {
    // base case
    if (root == null) return;
    
    // 利用定义,把左右子树拉平
    flatten(root.left);
    flatten(root.right);

    /**** 后序遍历位置 ****/
    // 1、左右子树已经被拉平成一条链表
    TreeNode left = root.left;
    TreeNode right = root.right;
    
    // 2、将左子树作为右子树
    root.left = null;
    root.right = left;

    // 3、将原先的右子树接到当前右子树的末端
    TreeNode p = root;
    while (p.right != null) {
        p = p.right;
    }
    p.right = right;/**<extend up -50><img src="/algo/images/二叉树系列/2.jpeg"> */
}
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

// 定义:将以 root 为根的树拉平为链表
void flatten(TreeNode* root) {
    // base case
    if (root == nullptr) return;

    // 利用定义,把左右子树拉平
    flatten(root->left);
    flatten(root->right);

    /**** 后序遍历位置 ****/
    // 1、左右子树已经被拉平成一条链表
    TreeNode* left = root->left;
    TreeNode* right = root->right;

    // 2、将左子树作为右子树
    root->left = nullptr;
    root->right = left;

    // 3、将原先的右子树接到当前右子树的末端
    TreeNode* p = root;
    while (p->right != nullptr) {
        p = p->right;
    }
    p->right = right;/**<extend up -50><img src="/algo/images/二叉树系列/2.jpeg"> */
}
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

def flatten(root: TreeNode) -> None:
    # base case
    if not root:
        return

    # 利用定义,把左右子树拉平
    flatten(root.left)
    flatten(root.right)

    # 后序遍历位置
    # 1、左右子树已经被拉平成一条链表
    left = root.left
    right = root.right

    # 2、将左子树作为右子树
    root.left = None
    root.right = left

    # 3、将原先的右子树接到当前右子树的末端
    p = root
    while p.right:
        p = p.right
    p.right = right
    """
    extend up -50>
    <figure><img src="/images/%e4%ba%8c%e5%8f%89%e6%a0%91%e7%b3%bb%e5%88%97/2.jpeg"
     class="shadow myimage"/>
</figure>
    """
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

// 定义:将以 root 为根的树拉平为链表
func flatten(root *TreeNode) {
    // base case
    if root == nil {
        return
    }

    // 利用定义,把左右子树拉平
    flatten(root.Left)
    flatten(root.Right)

    /**** 后序遍历位置 ****/
    // 1、左右子树已经被拉平成一条链表
    left := root.Left
    right := root.Right

    // 2、将左子树作为右子树
    root.Left = nil
    root.Right = left

    // 3、将原先的右子树接到当前右子树的末端
    p := root
    for p.Right != nil {
        p = p.Right
    }
    p.Right = right
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试,仅供参考,如有疑惑,可以参照我写的 java 代码对比查看。

// 定义:将以 root 为根的树拉平为链表
var flatten = function(root) {
    // base case
    if (root === null) return;

    // 利用定义,把左右子树拉平
    flatten(root.left);
    flatten(root.right);

    /**** 后序遍历位置 ****/
    // 1、左右子树已经被拉平成一条链表
    var left = root.left;
    var right = root.right;

    // 2、将左子树作为右子树
    root.left = null;
    root.right = left;

    // 3、将原先的右子树接到当前右子树的末端
    var p = root;
    while (p.right !== null) {
        p = p.right;
    }
    p.right = right;
};

🎃 代码可视化动画 🎃

你看,这就是递归的魅力,你说 flatten 函数是怎么把左右子树拉平的?

不容易说清楚,但是只要知道 flatten 的定义如此并利用这个定义,让每一个节点做它该做的事情,然后 flatten 函数就会按照定义工作。

至此,这道题也解决了,我们前文 k个一组翻转链表 的递归思路和本题也有一些类似。

最后,首尾呼应,再次默写二叉树解题总纲。

二叉树解题的思维模式分两类:

1、是否可以通过遍历一遍二叉树得到答案?如果可以,用一个 traverse 函数配合外部变量来实现,这叫「遍历」的思维模式。

2、是否可以定义一个递归函数,通过子问题(子树)的答案推导出原问题的答案?如果可以,写出这个递归函数的定义,并充分利用这个函数的返回值,这叫「分解问题」的思维模式。

无论使用哪种思维模式,你都需要思考:

如果单独抽出一个二叉树节点,它需要做什么事情?需要在什么时候(前/中/后序位置)做?其他的节点不用你操心,递归函数会帮你在所有节点上执行相同的操作。

希望你能仔细体会,并运用到所有二叉树题目上。

本文就到这里,更多经典的二叉树习题以及递归思维的训练,请参见 手把手带你刷通二叉树

接下来可阅读:


引用本文的题目

安装 我的 Chrome 刷题插件 点开下列题目可直接查看解题思路:

LeetCode 力扣
- 剑指 Offer 26. 树的子结构
- 剑指 Offer 27. 二叉树的镜像

引用本文的文章

_____________

《labuladong 的算法小抄》已经出版,关注公众号查看详情;后台回复关键词「进群」可加入算法群;回复「全家桶」可下载配套 PDF 和刷题全家桶

共同维护高质量学习环境,评论礼仪见这里,违者直接拉黑不解释