Q: 如何返回一颗子树的最后一个节点?

A: 如果有有右子树, 则最右节点在左子树上, 否则在左子树上

 

思路:

1. 题目要求转换要 in-place

2. 函数 preorder(root) 返回以 root 为根子树的最右节点, 同时完成 flatten 工作

 

代码:

代码的逻辑有些乱

class Solution {public:    void flatten(TreeNode *root) {		if(root == NULL)			return;        preorder(root);    }	TreeNode* preorder(TreeNode *root) {		if(root->left == NULL && root->right == NULL)			return root;		TreeNode *rc = root->right;		TreeNode *rl;		if(root->left != NULL) {			root->right = root->left;			rl = preorder(root->left);			rl->right =rc;		}		root->left = NULL;		if(rc != NULL)			return preorder(rc);		else			return rl; 	}};