LeetCode-二叉树

2024-01-22 19:53:22

二叉树的遍历，注意递归和非递归两种思路。

94. Binary Tree Inorder Traversal 二叉树中序遍历

https://leetcode.com/problems/binary-tree-inorder-traversal/

题目：给定二叉树，返回节点值的中序遍历。

思路：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        if(root == null) return list;
        inShow(list, root);
        return list;
    }
    
    public void inShow(List<Integer> l, TreeNode node) {
        if(node.left != null) {
            inShow(l, node.left);
        }
        l.add(node.val);
        if(node.right != null) {
            inShow(l, node.right);
        }
    }
}

100. Same Tree 相同的树

https://leetcode.com/problems/same-tree/

题目：给定两个二叉树，编写一个函数来检查它们是否相同。如果两个二叉树在结构上相同，且节点具有相同的值，则它们被认为是相同的。

思路：

①：判断两棵树是否相同和之前的判断两棵树是否对称都是一样的原理，利用深度优先搜索DFS来递归。

②：还有非递归的解法，因为二叉树的四种遍历(层序，先序，中序，后序)均有各自的迭代和递归的写法，这里我们先来看先序的迭代写法，相当于同时遍历两个数，然后每个节点都进行比较。

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if ((p != null && q == null) || (p == null && q != null) || (p.val != q.val)) return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

129. Sum Root to Leaf Numbers 求根节点到叶节点的值的总和

http://oj.leetcode.com/problems/sum-root-to-leaf-numbers/

题目：如果一个二叉树只包含从0到9的数字，那么每个根到叶的路径都可以表示一个数字.一个例子是根对叶路径1->2->3，它表示数字123。找出所有根到叶数的总和。注意：叶子是一个没有子节点的节点。

思路：

class Solution {
    int tot = 0;
    public int sumNumbers(TreeNode root) {
        if(root==null)
            return 0;
        calc(root,0);
        return tot;
    }
    
    public void calc(TreeNode root, int currsum) {
        currsum =currsum*10 + root.val;
        if(root.left==null && root.right==null){
            tot+=currsum;
            return;
        }
        if(root.left!=null)
            calc(root.left,currsum);
        if(root.right!=null)
            calc(root.right,currsum);
        return;
    }
}

144. Binary Tree Preorder Traversal 二叉树前序遍历

https://leetcode.com/problems/binary-tree-preorder-traversal/

题目：给定二叉树，返回其节点值的前序遍历。

思路：

class Solution {
    // 递归实现
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        if(root == null) return list;
        frontShow(list, root);
        return list;
    }
    
    public void frontShow(List<Integer> l, TreeNode node) {
        l.add(node.val);
        if(node.left != null) {
            frontShow(l, node.left);
        }
        if(node.right != null) {
            frontShow(l, node.right);
        }
    }
}

class Solution {
    // 非递归实现
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new LinkedList<Integer>();
        Stack<TreeNode> rights = new Stack<TreeNode>();
        while(root != null) {
            list.add(root.val);
            if(root.right != null) {
                rights.push(root.right);
            }
            root = root.left;
            if(root == null && !rights.isEmpty()) {
                root = rights.pop();
            }
        }
        return list;
    }
}

145. Binary Tree Postorder Traversal 二叉树后序遍历

https://leetcode.com/problems/binary-tree-postorder-traversal/

题目：给定二叉树，返回节点值的后序遍历。

思路：

class Solution {
    // 递归实现
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        if(root == null) return list;
        backShow(list, root);
        return list;
    }
    
    public void backShow(List<Integer> l, TreeNode node) {
        if(node.left != null) {
            backShow(l, node.left);
        }
        if(node.right != null) {
            backShow(l, node.right);
        }
        l.add(node.val);
    }
}

// TODO

码农公寓

相关文章