Algorithm Problem:Swap the left and right sub-tree in a binary tree without recursion

By | 2012 年 12 月 19 日

Just swap the tree nodes’ left and right child, in the post traversal order.
只需要在后序遍历的过程中,交换节点的左右子树即可。



Code

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void swapLeftAndRight(TreeNode *root) {
        bool forward = true;
        TreeNode *pre = NULL;
        stack trace;
        if(root) trace.push(root);
        
        while(trace.size()) {
            TreeNode *cur = trace.top();
            if(forward) {
                if(cur->left && pre != cur->left) {
                    trace.push(cur->left);
                } else {
                    forward = false;
                }
            } else {
                if(cur->right && pre != cur->right) {
                    trace.push(cur->right);
                    forward = true;
                } else {
                    //all the child has finished visit, then swap the left and right of cur
                    TreeNode *t = cur->left;
                    cur->left = cur->right;
                    cur->right = t;
                    
                    trace.pop();
                }
            }
            pre = cur;
        }
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注