二叉树/BinaryTree

94. 二叉树的中序遍历

package main
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}
// 左中右
func inorderTraversal(root *TreeNode) []int {
    var l []int
    //如果是空直接返回
    if root == nil {
        return nil
    }
    // 创建栈 递归从根源就是栈结构
    stack := make([]*TreeNode, 0)
    node := root
    // 只要当前节点不为空，或者栈不为空，就一直循环查找左节点
    for node != nil || len(stack) > 0 {
        //查找左节点
        if node != nil {
            // 将左节点放入栈中
            stack = append(stack, node)
            node = node.Left
        } else {
            // 获取站顶节点
            curr := stack[len(stack)-1]
            // 出栈操作
            stack = stack[:len(stack)-1]
            l = append(l, curr.Val)
            // 遍历右节点
            node = curr.Right
        }
    }
    return l
}
func main() {
    a := &TreeNode{
        Val: 1,
    }
    b := &TreeNode{
        Val: 2,
    }
    a.Left = b
    c := &TreeNode{
        Val: 3,
    }
    a.Right = c
    d := &TreeNode{
        Val: 4,
    }
    b.Left = d
    e := &TreeNode{
        Val: 5,
    }
    b.Right = e
    f := &TreeNode{
        Val: 6,
    }
    c.Left = f
    // 4,2,5,1,6,3
    inorderTraversal(a)
}

Java代码实现

public class Solution {
    public List < Integer > inorderTraversal(TreeNode root) {
        List < Integer > res = new ArrayList < > ();
        Stack < TreeNode > stack = new Stack < > ();
        TreeNode curr = root;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            res.add(curr.val);
            curr = curr.right;
        }
        return res;
    }
}

144. 二叉树的前序遍历

首先我们应该创建一个Stack用来存放节点，首先我们想要打印根节点的数据，此时Stack里面的内容为空，所以我们优先将头结点加入Stack，然后打印。
之后我们应该先打印左子树，然后右子树。所以先加入Stack的就是右子树，然后左子树。

import java.util.LinkedList;
import java.util.List;
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    };
}
public  class binary_tree_preorder_traversal_144 {
    public static 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;
    }
        public static void main(String[] args) {
            TreeNode one = new TreeNode(1);
            TreeNode two = new TreeNode(2);
            TreeNode three = new TreeNode(3);
            one.right = two;
            two.left = three;
            List<Integer> r = preorderTraversal(one);
            System.out.println(r);
        }
}

go 实现

package main
import "fmt"
// 前序遍历
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}
// 递归方法
func preorderTraversal(root *TreeNode) []int{
    if root==nil {
        return nil
    }
    fmt.Println(root.Val)
    preorderTraversal1(root.Left)
    preorderTraversal1(root.Right)
    return nil
}
// 中左右
func preorderTraversal1(root *TreeNode) []int {
    var l []int
    //如果是空直接返回
    if root == nil {
        return nil
    }
    // 创建栈 递归从根源就是栈结构
    stack := make([]*TreeNode, 0)
     curr := root
    // 只要当前节点不为空，或者栈不为空，就一直循环查找左节点
    for curr != nil || len(stack) > 0 {
        //查找左节点
        for (curr != nil){
            stack = append(stack,curr)
            fmt.Println(curr.Val)
            l = append(l,curr.Val)
            curr = curr.Left
        }
        curr = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        curr = curr.Right
    }
    return l
}
// 中左右
func preorderTraversal2(root *TreeNode) []int {
    var l []int
    //如果是空直接返回
    if root == nil {
        return nil
    }
    // 创建栈 递归从根源就是栈结构
    stack := make([]*TreeNode, 0)
    stack = append(stack,root)
    // 只要当前节点不为空，或者栈不为空，就一直循环查找左节点
    for  len(stack) > 0 {
         curr := stack[len(stack)-1]
         stack = stack[:len(stack)-1]
         fmt.Println(curr.Val)
         l = append(l,curr.Val)
        if curr.Right != nil {
            stack = append(stack,curr.Right)
        }
        if curr.Left != nil {
            stack = append(stack,curr.Left)
        }
    }
    return l
}
//https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
func main() {
    a := &TreeNode{
        Val: 1,
    }
    b := &TreeNode{
        Val: 2,
    }
    a.Left = b
    c := &TreeNode{
        Val: 3,
    }
    a.Right = c
    d := &TreeNode{
        Val: 4,
    }
    b.Left = d
    e := &TreeNode{
        Val: 5,
    }
    b.Right = e
    f := &TreeNode{
        Val: 6,
    }
    c.Left = f
    // 1 2 4 5 3 6
    preorderTraversal1(a)
}