LintCode -- 이 진 트 리 뒤 집기 (비 재 귀적)

LintCode -- invert - binary - tree (이 진 트 리 뒤 집기 - 비 재 귀적)
원본 링크:http://www.lintcode.com/zh-cn/problem/invert-binary-tree/
두 갈래 나 무 를 뒤집다.
본보기

  1         1
 / \       / \
2   3  => 3   2
   /       \
  4         4

도전 하 다.
재 귀 는 물론 가능 하지만, 재 귀 하지 않 는 것 을 쓸 수 있 습 니까?
분석:
재 귀 는 어렵 지 않 습 니 다. 전, 중, 후 순 으로 옮 겨 다 니 며 스 택 의 형식 으로 결산 점 을 저장 합 니 다.
****   시간 복잡 도 O (n). 공간 복잡 도 O (n) ****
이전 순서 옮 겨 다 니 기:

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param root: a TreeNode, the root of the binary tree
     * @return: nothing
     */
    void invertBinaryTree(TreeNode *root) {     //DLR  diedai
        // write your code here
        TreeNode *x = root;
        TreeNode *tmp;
        vector<TreeNode*> p;
        while(x != NULL || p.size() != 0){
            tmp = x->left;
            x->left = x->right;
            x->right = tmp;
            if (x->right != NULL)
                p.push_back(x->right);
            x = x->left;
            if (x == NULL && p.size() != 0){
                x = p.back();
                p.pop_back();
            }
        }
    }
};

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""
class Solution:
    # @param root: a TreeNode, the root of the binary tree
    # @return: nothing
    def invertBinaryTree(self, root):
        # write your code here        DLR   diedai
        x = root
        stackk = [x for i in range(1000)]
        siz = 0
        while x is not None or siz != 0:
            (x.left, x.right) = (x.right, x.left)
            if x.right is not None:
                siz += 1
                stackk[siz] = x.right
            x = x.left
            if x is None and siz != 0:
                x = stackk[siz]
                siz -= 1

중간 순서 옮 겨 다 니 기:

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param root: a TreeNode, the root of the binary tree
     * @return: nothing
     */
    void invertBinaryTree(TreeNode *root) {     //LDR   diedai
        // write your code here
        TreeNode *x = root;
        vector<TreeNode *> p;
        while(x != NULL || p.size() != 0){
            while(x != NULL){
                p.push_back(x);
                x = x->left;
            }
        x = p.back();
        p.pop_back();
        TreeNode *tmp;
        tmp = x->left;
        x->left = x->right;
        x->right = tmp;
        x = x->left;
        }
    }
};

다음 순서 옮 겨 다 니 기:

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param root: a TreeNode, the root of the binary tree
     * @return: nothing
     */
    void invertBinaryTree(TreeNode *root) {     //LRD  diedai
        // write your code here
        TreeNode *x = root;
        int a = 1;
        vector<TreeNode *> s;
        while(a == 1){
            while(x->left != NULL || x->right != NULL){
                if(x->left != NULL){
                    s.push_back(x);
                    x = x->left;
                }
                else{
                    s.push_back(x);
                    x = x->right;
                }
            }
            TreeNode *y = s.back();
            while (x == y->right || (x == y->left && y->right == NULL)){
                TreeNode *tmp = y->left;
                y->left = y->right;
                y->right = tmp;
                s.pop_back();
                if (s.size() == 0){
                    a = 0;
                    break;
                }
                x = y;
                y = s.back();
            }
            if (x == y->left) x = y->right;
        }
    }
};

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root: a TreeNode, the root of the binary tree
     * @return: nothing
     */
    public void invertBinaryTree(TreeNode root) {
        // write your code here             LRD   diedai
        TreeNode x = root;
        int a = 1;
        Vector <TreeNode > s = new Vector<TreeNode>(); 
        while(a == 1){
            while(x.left != null || x.right != null){
                if(x.left != null){
                    s.addElement(x);
                    x = x.left;
                }
                else{
                    s.addElement(x);
                    x = x.right;
                }
            }
            TreeNode y = s.get(s.size()-1);
            while (x == y.right || (x == y.left && y.right == null)){
                TreeNode tmp = y.left;
                y.left = y.right;
                y.right = tmp;
                s.remove(s.size()-1);  
                if (s.size() == 0){
                    a = 0;
                    break;
                }
                x = y;
                y = s.get(s.size()-1);
            }
            if (x == y.left) x = y.right;
        }
    }
};