leetcode144二叉树的前序遍历

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [1,2,3]

func preorderTraversal(root *TreeNode) []int {
    cur := root
    stack := make([]*TreeNode, 0)
    res := make([]int, 0)
    for cur != nil {
        for cur != nil {
            stack = append(stack, cur)
            res = append(res, cur.Val)
            cur = cur.Left
        }
        if len(stack) == 0 {
            break
        }
        for cur = stack[len(stack)-1].Right; ; cur = stack[len(stack)-1].Right{
            stack = stack[:len(stack)-1]
            /*
            for i := 0; i < len(stack); i++ {
                fmt.Print(stack[i].Val, " ")    
            }
            fmt.Println()*/
            
            
            if len(stack) == 0 || cur != nil {
                break
            }
        }
    }
    return res
}

func preorderTraversal(root *TreeNode) []int {
  if root == nil {
        return nil
    }
    var rootTemp = root
    var stack []*TreeNode
    var ret []int
    for rootTemp != nil || len(stack) != 0 {
        if rootTemp != nil {
            ret = append(ret, rootTemp.Val)
            stack = append(stack, rootTemp)
            rootTemp = rootTemp.Left
        } else {
            rootTemp = stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            //ret = append(ret, rootTemp.Val)
            rootTemp = rootTemp.Right
        }
    }
    return ret  
}

class Solution {
  public List<Integer> preorderTraversal(TreeNode root) {
    LinkedList<TreeNode> stack = new LinkedList<>();
    LinkedList<Integer> output = new LinkedList<>();
    if (root == null) {
      return output;
    }

    stack.add(root);
    while (!stack.isEmpty()) {
      TreeNode node = stack.pollLast();
      output.add(node.val);
      if (node.right != null) {
        stack.add(node.right);
      }
      if (node.left != null) {
        stack.add(node.left);
      }
    }
    return output;
  }
}

class Solution {
  public List<Integer> preorderTraversal(TreeNode root) {
    LinkedList<Integer> output = new LinkedList<>();

    TreeNode node = root;
    while (node != null) {
      if (node.left == null) {
        output.add(node.val);
        node = node.right;
      }
      else {
        TreeNode predecessor = node.left;
        while ((predecessor.right != null) && (predecessor.right != node)) {
          predecessor = predecessor.right;
        }

        if (predecessor.right == null) {
          output.add(node.val);
          predecessor.right = node;
          node = node.left;
        }
        else{
          predecessor.right = null;
          node = node.right;
        }
      }
    }
    return output;
  }
}