分类 编程 下的文章

二叉树的前序遍历


给定一个二叉树,返回它的 *前序* 遍历。 ``` 输入: [1,null,2,3] 1 \ 2 / 3 输出: [1,2,3] ``` 递归实现: ``` vector preorderTraversal(TreeNode* root) { vector chain = {}; preorderTraversalRecur(root, &chain); return chain; } void preorderTraversalRecur(TreeNode* root, vector* chain) { if (!root) { return; } chain->push_back(root->val); preorderTraversalRecur(root->left, chain); preorderTraversalRecur(root->right, chain); } ```

从中序与后序遍历序列构造二叉树


根据一棵树的中序遍历与后序遍历构造二叉树。 例如,给出 ``` 中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3] ``` 返回如下的二叉树: ``` 3 / \ 9 20 / \ 15 7 ``` 解题思路:后序遍历最后一个元素为根节点m,右侧元素个数为n,右节点为m-1,左节点为m-1-n。 ``` typedef vector::iterator Iter; TreeNode *buildTreeRecur(Iter istart, Iter iend, Iter pstart, Iter pend) { if (istart == iend) return NULL; int val = *pstart; Iter iter = find(istart, iend, val); TreeNode* root = new TreeNode(val); size_t length = distance(iter, iend) - 1; root->left = buildTreeRecur(istart, iter, pstart + 1 + length, pend); root->right = buildTreeRecur(iter + 1, iend, pstart + 1, pend); return root; } TreeNode *buildTree(vector &inorder, vector &postorder) { reverse(postorder.begin(), postorder.end()); return buildTreeRecur(inorder.begin(), inorder.end(), postorder.begin(), postorder.end()); } ```

从前序遍历和中序遍历树构造二叉树


从前序与中序遍历序列构造二叉树。 例如,给出: ``` 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] ``` 返回的二叉树: ``` 3 / \ 9 20 / \ 15 7 ``` 解题思路: 无论是前序还是中序遍历,左子节点必然相等,前序的第一个元素为根节点,中序的第一个元素为最左侧的。若左边一个有n个元素,则根节点的为m,左树m+1,右树m+n+1。 ``` typedef vector::iterator Iter; TreeNode *buildTreeRecur(Iter istart, Iter iend, Iter pstart, Iter pend) { if (istart == iend)return NULL; int rootval = *pstart; Iter iterroot = find(istart, iend, rootval); TreeNode *res = new TreeNode(rootval); res->left = buildTreeRecur(istart, iterroot, pstart + 1, pend); res->right = buildTreeRecur(iterroot + 1, iend, pstart + 1 + (iterroot - istart), pend); return res; } TreeNode *buildTree(vector &preorder, vector &inorder) { return buildTreeRecur(inorder.begin(), inorder.end(), preorder.begin(), preorder.end()); } ```