喜刷刷: in-order traversal

Showing posts with label in-order traversal. Show all posts

Wednesday, November 12, 2014

[LeetCode] Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

思路：
非常巧妙的题目，解答时参考了这篇文章： http://leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html

这题和Convert Sorted Array to Binary Search Tree那题看上去很像，但是从array变成了linked list，就不能O(1)寻找中间节点了。一种直接的修改就是每次遍历一半的节点来找寻中间节点。如何在不知道linked list总长的情况下遍历一半节点？双指针策略，快指针一次走2个节点，慢指针一次走1个节点，当快指针到尾部时，慢指针对应的即为中间节点。但这种方法的时间复杂度为O(N logN)：每层递归一共访问N/2个节点，一共log N层递归（对应树的高度）。

对于构建N节点的binary tree来说理论上算法复杂度最少只能到O(N)，因为生成N个节点本身就需要O(N)。要达到O(N)复杂度的算法，就不能反复遍历来查找中间节点，而只能顺序边访问linked list边构建树。这里的关键是利用构建left subtree的递归，来找寻middle节点。即构建left subtree的时候需要返回两个值：left subtree的root节点，以及整个left subtree在linked list中的下一个节点，即middle节点，也是整个left subtree的parent节点。

class Solution {
public:
    TreeNode *sortedListToBST(ListNode *head) {
        int listLen = 0;
        ListNode *cur = head;
        while(cur) {
            listLen++;
            cur = cur->next;
        }
        return sortedListToBST(head, 0, listLen-1);
    }
    
    TreeNode *sortedListToBST(ListNode *&head, int start, int end) {
        if(start>end) return NULL;
        int mid = start + (end-start)/2;
        TreeNode *leftChild = sortedListToBST(head, start, mid-1);
        TreeNode *root = new TreeNode(head->val);
        head = head->next;
        TreeNode *rightChild = sortedListToBST(head, mid+1, end);
        root->left = leftChild;
        root->right = rightChild;
        return root;
    }
};

总结：

这个方法非常不容易理解

TreeNode *sortedListToBST(ListNode *&head, int start, int end)

这个函数所做的是将*head为头的linked list构建成一个BST，然后返回BST的root，而同时，也将head移动到linked list中第end+1个节点。因为*head既是输入参数，也是返回参数，所以这里用到了指针的引用*&head。注意不能错写成了&*head。理解*&的方法是从右向左读：首先是一个引用，然后是一个对指针的引用，最后是一个对ListNode指针的引用。

那么当left subtree构建完成后，head指向了mid，构建mid树节点。然后后移head到right subtree在linked list中的头节点。继续递归构建right subtree.

跑一个例子：

linked list: 0->1->2->NULL

call (head(0), 0, 2)

mid = 1

node(1), head(2)

/ \

call (head(0), 0, 0) call (head(2), 2, 2)

mid = 0 mid = 2

node(0), head(1) node(2), head(NULL)

/ \ / \

call (head(0), 0, -1) call (head(0), 1, 0) call (head(2), 2, 1) call (head(0), 2, 1)

return NULL return NULL return NULL return NULL

最终结果：

/ \

0 2

Tuesday, November 11, 2014

[LeetCode] Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

思路：

和Construct Binary Tree from Preorder and Inorder Traversal雷同，关键在于在inorder中找root，从而得以分割left/right subtree，并通过递归来重构。区别仅仅在于对postorder来说root为序列最后一个节点，以及left/right subtree左右边界index的计算稍有不同。

class Solution {
public:
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
        if(inorder.size()!=postorder.size()) return NULL;
        int n = inorder.size();
        return buildBT(inorder, postorder, 0, n-1, 0, n-1);
    }
    
    TreeNode *buildBT(vector<int> &inorder, vector<int> &postorder, int s1, int e1, int s2, int e2) {
        if(s1>e1 || s2>e2) return NULL;
        TreeNode *root = new TreeNode(postorder[e2]);
        int rootIndex = -1;
        for(int i=s1; i<=e1; i++) {
            if(inorder[i]==root->val) {
                rootIndex = i;
                break;
            }
        }
        if(rootIndex==-1) return NULL;
        int leftTreeSize = rootIndex - s1;
        int rightTreeSize = e1 - rootIndex;
        
        root->left = buildBT(inorder, postorder, s1, rootIndex-1, s2, s2+leftTreeSize-1);
        root->right = buildBT(inorder, postorder, rootIndex+1, e1, e2-rightTreeSize, e2-1);
        return root;
    }
};

[LeetCode] Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

思路：

Binary tree一共3种访问顺序：preorder, inorder, postorder。这道题目的推广就是给定一个binary tree的两种访问顺序，重构该binary tree。这类题目给定的两个排序中，如果包括了inorder，且没有重复元素，就非常好解了。解这类题有两个关键点：

1. 在inorder中寻找root的位置，从而从序列中分割出左右子树。

Inorder: left subtree | root | right subtree

Preorder: root | left subtree | right subtree

Postorder: left subtree | right subtree | root

可见root是preorder序列的第一个节点，也是postorder的最后一个节点。所以给定这两个序列的任意一个我们即知道了root->val。通过搜索inorder序列，可以定位root所在的位置，从而也得到了left subtree和right subtree的节点数。

2. 递归构建

当root，left/right subtree都确定后

root->left = construct(inorder(left subtree), preorder(left subtree))

root->right = construct(inorder(right subtree), preorder(right subtree))

class Solution {
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        if(preorder.size()!=inorder.size()) return NULL;
        int n = preorder.size();
        return buildBT(preorder, inorder, 0, n-1, 0, n-1);
    }
    
    TreeNode *buildBT(vector<int> &preorder, vector<int> &inorder, int s1, int e1, int s2, int e2) {
        if(s1>e1 || s2>e2) return NULL;
        TreeNode *root = new TreeNode(preorder[s1]);
        
        int rootIndex = -1; // root index in inorder
        for(int i=s2; i<=e2; i++) {
            if(inorder[i]==root->val) {
                rootIndex = i;
            }
        }
        if(rootIndex==-1) return NULL;
        int leftTreeSize = rootIndex - s2;
        int rightTreeSize = e2 - rootIndex;
        
        root->left = buildBT(preorder, inorder, s1+1, s1+leftTreeSize, s2, rootIndex-1);
        root->right = buildBT(preorder, inorder, e1-rightTreeSize+1, e1, rootIndex+1, e2);
        return root;
    }
};

Monday, November 10, 2014

[LeetCode] Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

1. 递归解法：

连题目都说recursive solution is trivial，没啥好说的，这解法两分钟写不出来就要被鄙视了。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> allNodeValues;
        inorderTrav(root, allNodeValues);
        return allNodeValues;
    }
    
    void inorderTrav(TreeNode *root, vector<int> &allNodeValues) {
        if(!root) return;
        inorderTrav(root->left, allNodeValues);
        allNodeValues.push_back(root->val);
        inorderTrav(root->right, allNodeValues);
    }
};

2. 迭代解法：

面试中应该不会只考递归这么简单。所以迭代解法才是真正的重点。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> allNodeValues;
        TreeNode *cur = root; 
        stack<TreeNode*> s;
        
        while(cur || !s.empty()) {
            if(!cur) {
                cur = s.top();
                s.pop();
                allNodeValues.push_back(cur->val);
                cur = cur->right;
            }
            else {
                s.push(cur);
                cur = cur->left;
            }
        }
        
        return allNodeValues;
    }
};

[LeetCode] Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

解法1：min/max法

这是我觉得最直接了当、简洁易懂的方法：

1. 先top-down递归，由父节点来传递子节点的值所允许的范围minVal < x->val < maxVal。如果该条件不符合，返回false。

2. 如果上述条件符合，只说明当前节点x本身符合BST条件。还需要bottom-up递归来检查当前节点的左右子树是否也都符合BST条件。左子树的取值范围为(minVal, x->val)，右子树取值范围为(x->val, maxVal)。

class Solution {
public:
    bool isValidBST(TreeNode *root) {
        return validateBST(root, INT_MIN, INT_MAX);
    }
    
    bool validateBST(TreeNode *root, int minVal, int maxVal) {
        if(!root) return true;
        if(root->val<=minVal || root->val>=maxVal) return false;
        return validateBST(root->left, minVal, root->val) && validateBST(root->right, root->val, maxVal);
    }
};

解法2：inorder traversal法
1. 对一个BST进行inorder traverse，必然会得到一个严格单调递增序列，否则则是invalid BST。

2. Inorder traverse时并不需要记录下整个访问过的序列，而只需要保存前一个访问的节点数值就可以了。

class Solution {
public:
    bool isValidBST(TreeNode *root) {
        int curMax = INT_MIN;
        return validateBST(root, curMax);
    }
    
    bool validateBST(TreeNode *root, int &curMax) {
        if(!root) return true;
        if(!validateBST(root->left, curMax)) return false;
        if(curMax >= root->val) return false;
        curMax = root->val;
        return validateBST(root->right, curMax);
    }
};

ln 10:检验左子树是否valid，并通过引用得到左子树的最大值curMax。

ln 11-12:在左子树valid的情况下，判断当前节点是否大于curMax。在当前节点也valid的情况下，更新curMax为当前节点。

ln 13:当左子树和当前节点都valid时，返回右子树的检验结果即可。